1 Introduction

Here, I write code that tests the whether forward feature selection makes sense in the context of unsupervised randomForest.

2 VarReduct

usVr = function(x, seed=42) {
    set.seed(seed)
    x_fake = x %>% mutate(across(everything(), ~ sample(.x, size=nrow(x))))
    varReduct(predictor_vars=rbind(x, x_fake),
                response_var=factor(c(rep('real', nrow(x)), rep('fake', nrow(x_fake)))),
                varReduct_method='forwardSelect',
                algo='randomForest',
                select_method='elbow_and_gap',
                trace=F,
#                num_jobs=1,
                seed=42)
}
usrf = function(x, seed=42, ntree=1000) {
    set.seed(seed)
    x_fake = x %>% mutate(across(everything(), ~ sample(.x, size=nrow(x))))
    rf = randomForest::randomForest(x=rbind(x, x_fake),
                      y=factor(c(rep('real', nrow(x)), rep('fake', nrow(x_fake)))),
                      importance=T,
                      keep.forest=F,
                      ntree=ntree
                      )
    rf
}
varimpcomp_plot = function(...) {
    dots = list(...)
    if(is.null(names(dots))) {
        names(dots) = unlist(lapply(substitute(list(...))[-1], deparse))
    }
    ks = sapply(dots, function(x) nrow(importance(x)))
    tmp = bind_rows(lapply(seq_along(dots), function(i) {
        x = dots[[i]]
        tmp = importance(x) %>% 
            tibble::rownames_to_column('variable') %>% 
            mutate(run=names(dots)[i]) %>%
            mutate(vimp_rank=rank(-overall))
        if(ks[i] > min(ks)) {
            tmp$vimp_rank = tmp$vimp_rank - 1
        }
        tmp
    }))
    tmp2 = tmp %>% group_by(variable) %>%
        summarize(vimp_rank=mean(vimp_rank)) %>%
        arrange(-vimp_rank) %>%
        pull(variable)
    tmp$variable = factor(tmp$variable, levels=tmp2)
    ggplot(tmp) +
        aes(x=vimp_rank, y=variable) +
        geom_segment(aes(xend=0, group=run), color="grey69", linetype="dashed",
                     position=position_dodge(width=0.5)) +
        geom_point(aes(color=run), position=position_dodge(width=0.5)) +
        scale_color_brewer(name="", palette="Dark2") +
        xlab("rank( variable importance )") +
        ylab("") +
        scale_x_continuous(breaks=scales::breaks_pretty()) +
        guides(colour=guide_legend(reverse=T, position="bottom")) +
        theme_minimal()
}
vimp_spearman_plot = function(...) {
    dots = list(...)
    if(is.null(names(dots))) {
        names(dots) = unlist(lapply(substitute(list(...))[-1], deparse))
    }
    vimps = lapply(names(dots), function(name) {
        x = dots[[name]]
        tmp = importance(x) %>% 
            tibble::rownames_to_column('variable') %>%
            select(!important)
        colnames(tmp)[colnames(tmp) == 'overall'] = name
        tmp
    })
    tmp = reduce(vimps, inner_join, by='variable') %>%
        tibble::column_to_rownames('variable')
    tmp = cor(tmp, method='spearman')
    tmp = as.data.frame(tmp) %>%
        tibble::rownames_to_column('var1') %>%
        pivot_longer(-var1, names_to='var2', values_to='value') %>%
        mutate(var1 = factor(var1, levels=colnames(tmp)),
               var2 = factor(var2, levels=colnames(tmp)))
    ggplot(tmp) +
        aes(x=var1, y=var2, fill=value) +
        geom_tile() +
        geom_text(aes(label=round(value, 2))) +
        scale_fill_gradient2(name="Spearman\ncorrelation", midpoint=0, low="blue", 
                             mid="white", high="red", limits=c(-1, 1)) +
        xlab("") +
        ylab("") +
        theme_minimal() +
        theme(axis.text.x = element_text(angle=60, vjust=1, hjust=1)) +
        coord_fixed()
}
summary2df = function(x) {
    data.frame(unclass(summary(x)), check.names = FALSE, stringsAsFactors = FALSE) %>%
        `rownames<-`( NULL )
}
combineDataSets = function(..., seed=42) {
    set.seed(seed)
    dfs = list(...)
    if(is.null(names(dfs))) {
        names(dfs) = unlist(lapply(substitute(list(...))[-1], deparse))
    }
    n = min(sapply(dfs, nrow))
    bind_cols(lapply(names(dfs), function(name) {
        df = dfs[[name]]
        colnames(df) = paste(name, colnames(df), sep='__')
        if(nrow(df) == n) { return(df) }
#        k = df %>% pull(ends_with('Class')) %>% unique() %>% length()
        df %>%# group_by(across(ends_with('Class'))) %>%
            slice_sample(n=n) 
    }))
}

3 Iris data set

iris summary
summary2df(iris)
Sepal.Length Sepal.Width Petal.Length Petal.Width Species
Min. :4.30 Min. :2.00 Min. :1.00 Min. :0.1 setosa :50
1st Qu.:5.10 1st Qu.:2.80 1st Qu.:1.60 1st Qu.:0.3 versicolor:50
Median :5.80 Median :3.00 Median :4.35 Median :1.3 virginica :50
Mean :5.84 Mean :3.06 Mean :3.76 Mean :1.2 NA
3rd Qu.:6.40 3rd Qu.:3.30 3rd Qu.:5.10 3rd Qu.:1.8 NA
Max. :7.90 Max. :4.40 Max. :6.90 Max. :2.5 NA
supervised run iris
vr1 = cache_rds({
    varReduct(predictor_vars=iris[,1:4],
                response_var=factor(iris$Species),
                varReduct_method='forwardSelect',
                algo='randomForest',
                trace=F,
                num_jobs=4,
                seed=42)
}, rerun=F, clean=T)
vr1$best_iter
vr1$eval_vec
vr1$num_vars_vec
importance(vr1)
## eval_type 
##         2 
## $err
## [1] 0.07333 0.03333
## 
## $aic
## [1] 2868.74   37.76
## 
## $aicc
## [1] 2868.77   37.84
## 
## [1] 1 2
overall important
Petal.Length 475.32 TRUE
Petal.Width 460.21 TRUE
Sepal.Length 154.88 FALSE
Sepal.Width 69.21 FALSE
unsupervised run with true labels
vr2 = cache_rds({
    usVr(iris)
}, rerun=F, clean=T)
vr2$best_iter
vr2$eval_vec
vr2$num_vars_vec
importance(vr2)
## eval_type 
##         0 
## $err
## [1] 0.82000 0.17667 0.08333
## 
## $aic
## [1] 461.6 321.8 217.9
## 
## $aicc
## [1] 461.6 321.8 218.0
## 
## [1] 1 2 3
overall important
Species 1014.7 TRUE
Petal.Length 968.1 TRUE
Petal.Width 910.3 TRUE
Sepal.Length 753.2 TRUE
Sepal.Width 410.5 TRUE
unsupervised run without true labels
vr3 = cache_rds({
    usVr(iris[,1:4])
}, rerun=F, clean=T)
vr3$best_iter
vr3$eval_vec
vr3$num_vars_vec
importance(vr3)
## eval_type 
##         0 
## $err
## [1] 0.9967 0.3200 0.1700
## 
## $aic
## [1] 639.2 393.5 295.5
## 
## $aicc
## [1] 639.2 393.5 295.5
## 
## [1] 1 2 3
overall important
Petal.Length 969.3 TRUE
Petal.Width 887.9 TRUE
Sepal.Length 867.9 TRUE
Sepal.Width 474.7 TRUE
p1 = varimpcomp_plot(supervised=vr1, unsupervised_wtl=vr2, unsupervised_wotl=vr3)
p2 = vimp_spearman_plot(supervised=vr1, unsupervised_wtl=vr2, unsupervised_wotl=vr3)
p1 + p2

plot_vr = function(vr) {
    tmp = as.data.frame(vr) %>%
        mutate(across(c(AIC, `Corrected AIC`, `Out-of-bag error`), 
                      ~ if(max(.x) == 0) 0 else .x/max(.x))) %>%
        pivot_longer(c(AIC, `Corrected AIC`, `Out-of-bag error`))
    ggplot(tmp) +
        aes(x=`Number of Variables`, y=value, color=name) +
        geom_line(alpha=0.5) +
        geom_point(alpha=0.5) +
        scale_color_brewer(name="", palette="Dark2") +
        scale_x_continuous(breaks=scales::breaks_pretty(6)) +
        ylab("Relative value") +
        theme_minimal()
}
plot_vr(vr2) / plot_vr(vr3) + plot_layout(guides='collect')

Observations

  • Including the true class labels, the true class labels are selected as the most important feature when doing unsupervised feature selection
  • The ordering of the features is the exact same whether including true labels or not compared to using supervised randomForest
    • I tested this with a different seed before, and there was one swap (the Petal features), indicating there is some stochasticity in it

3.1 Closer look at AIC in iris

imp = importance(vr3)
rfs = cache_rds({
    lapply(1:nrow(imp), function(i) {
        vars = rownames(imp)[1:i]    
        usrf(iris[,vars,drop=F], ntree=5000)
    })
}, rerun=F, clean=T)
y_true = rfs[[3]]$y
tmp = data.frame(
    pred_real1 = rfs[[1]]$votes[,1],
    pred_real2 = rfs[[2]]$votes[,1],
    pred_real3 = rfs[[3]]$votes[,1],
    pred_real4 = rfs[[4]]$votes[,1],
    class = rep(c('real', 'fake'), each=nrow(iris)),
    sample = 1:(2*nrow(iris))
) %>% pivot_longer(!c(class, sample))
ggplot(tmp) +
    geom_point(aes(x=sample, y=value, color=name, shape=class), 
               alpha=0.5) +
    ylab('Proportion votes for fake class') +
    theme_minimal()

aic_fixed = sapply(seq_along(rfs), function(i) {
   clfAIC(y_true[1:nrow(iris)], y_pred=rfs[[i]]$votes[1:nrow(iris),], k=i)
})
tmp = as.data.frame(vr3) %>%
    mutate(across(c(AIC, `Corrected AIC`, `Out-of-bag error`), 
                  ~ if(max(.x) == 0) 0 else .x/max(.x))) %>%
    pivot_longer(c(AIC, `Corrected AIC`, `Out-of-bag error`))
tmp2 = data.frame(NA, seq_along(rfs), NA, NA, NA, NA, "AIC_observed_only", aic_fixed/max(aic_fixed))
colnames(tmp2) = colnames(tmp)
tmp = bind_rows(tmp, tmp2)
ggplot(tmp) +
    aes(x=`Number of Variables`, y=value, color=name) +
    geom_line(alpha=0.5) +
    geom_point(alpha=0.5) +
    scale_color_brewer(name="", palette="Dark2") +
    scale_x_continuous(breaks=scales::breaks_pretty(6)) +
    ylim(0, 1) +
    ylab("Relative value") +
    theme_minimal()

4 Breast Cancer

breast cancer summary
data("BreastCancer", package = "mlbench")
BreastCancer = BreastCancer %>% 
    select(!Id) %>%
    mutate(across(!Class, as.numeric)) %>%
    filter(!is.na(Bare.nuclei))
summary2df(BreastCancer)
Cl.thickness Cell.size Cell.shape Marg.adhesion Epith.c.size Bare.nuclei Bl.cromatin Normal.nucleoli Mitoses Class
Min. : 1.00 Min. : 1.00 Min. : 1.00 Min. : 1.00 Min. : 1.00 Min. : 1.00 Min. : 1.00 Min. : 1.00 Min. :1.00 benign :444
1st Qu.: 2.00 1st Qu.: 1.00 1st Qu.: 1.00 1st Qu.: 1.00 1st Qu.: 2.00 1st Qu.: 1.00 1st Qu.: 2.00 1st Qu.: 1.00 1st Qu.:1.00 malignant:239
Median : 4.00 Median : 1.00 Median : 1.00 Median : 1.00 Median : 2.00 Median : 1.00 Median : 3.00 Median : 1.00 Median :1.00 NA
Mean : 4.44 Mean : 3.15 Mean : 3.21 Mean : 2.83 Mean : 3.23 Mean : 3.54 Mean : 3.44 Mean : 2.87 Mean :1.58 NA
3rd Qu.: 6.00 3rd Qu.: 5.00 3rd Qu.: 5.00 3rd Qu.: 4.00 3rd Qu.: 4.00 3rd Qu.: 6.00 3rd Qu.: 5.00 3rd Qu.: 4.00 3rd Qu.:1.00 NA
Max. :10.00 Max. :10.00 Max. :10.00 Max. :10.00 Max. :10.00 Max. :10.00 Max. :10.00 Max. :10.00 Max. :9.00 NA
supervised run breast cancer
vr1 = cache_rds({
    varReduct(predictor_vars=BreastCancer %>% select(-Class),
                response_var=factor(BreastCancer$Class),
                varReduct_method='forwardSelect',
                algo='randomForest',
                trace=F,
                preprocess=F,
                seed=42)
}, rerun=F, clean=T)
vr1$best_iter
vr1$eval_vec
vr1$num_vars_vec
importance(vr1)
## eval_type 
##         0 
## $err
## [1] 0.08785 0.04832
## 
## $aic
## [1] 38519  3009
## 
## $aicc
## [1] 38519  3009
## 
## [1] 1 2
overall important
Bare.nuclei 387.95 TRUE
Cell.shape 281.19 TRUE
Cell.size 277.02 TRUE
Cl.thickness 275.58 TRUE
Bl.cromatin 235.84 TRUE
Marg.adhesion 173.01 TRUE
Normal.nucleoli 161.45 TRUE
Epith.c.size 157.22 TRUE
Mitoses 87.44 TRUE
unsupervised run with true labels breast cancer
vr2 = cache_rds({
    usVr(BreastCancer)
}, rerun=F, clean=T)
vr2$best_iter
vr2$eval_vec
vr2$num_vars_vec
importance(vr2)
## eval_type 
##         3 
## $err
## [1] 0.67862 0.32138 0.20791 0.15886 0.14275 0.11493 0.09810 0.08638
## 
## $aic
## [1]   2056   1857   1534 115519  49126  44587  26117  14783
## 
## $aicc
## [1]   2056   1857   1534 115519  49126  44587  26117  14784
## 
## [1] 1 2 3 4 5 6 7 8
overall important
Cell.size 1411.0 TRUE
Class 1400.6 TRUE
Cell.shape 1390.7 TRUE
Bare.nuclei 1062.7 FALSE
Cl.thickness 1043.7 FALSE
Normal.nucleoli 1024.8 FALSE
Bl.cromatin 980.7 FALSE
Marg.adhesion 905.7 FALSE
Epith.c.size 747.3 FALSE
Mitoses 384.5 FALSE
unsupervised run without true labels breast cancer
vr3 = cache_rds({
    usVr(BreastCancer[,1:(ncol(BreastCancer)-1)])
}, rerun=F, clean=T)
vr3$best_iter
vr3$eval_vec
vr3$num_vars_vec
importance(vr3)
## eval_type 
##         3 
## $err
## [1] 0.7160 0.3551 0.2328 0.1977 0.1662 0.1362 0.1186 0.1025
## 
## $aic
## [1]   2053   2125   1640 105788  66036  56003  29147  19166
## 
## $aicc
## [1]   2053   2125   1640 105788  66036  56003  29147  19166
## 
## [1] 1 2 3 4 5 6 7 8
overall important
Cell.shape 1530.8 TRUE
Bare.nuclei 1318.0 TRUE
Cell.size 1217.0 TRUE
Normal.nucleoli 1161.0 FALSE
Marg.adhesion 1123.7 FALSE
Bl.cromatin 1084.2 FALSE
Cl.thickness 1061.4 FALSE
Epith.c.size 1044.5 FALSE
Mitoses 535.2 FALSE
p1 = varimpcomp_plot(supervised=vr1, unsupervised_wtl=vr2, unsupervised_wotl=vr3)
p2 = vimp_spearman_plot(supervised=vr1, unsupervised_wtl=vr2, unsupervised_wotl=vr3)
p1 + p2

plot_vr(vr2) / plot_vr(vr3) + plot_layout(guides='collect')

4.1 Closer look at AIC in breast cancer

imp = importance(vr2)
rfs = cache_rds({
    lapply(1:nrow(imp), function(i) {
        vars = rownames(imp)[1:i]    
        usrf(BreastCancer[,vars,drop=F], ntree=5000)
    })
}, rerun=F, clean=T)
y_true = rfs[[3]]$y
tmp = data.frame(
    pred_real3 = rfs[[3]]$votes[,1],
    pred_real4 = rfs[[4]]$votes[,1],
    class = rep(c('real', 'fake'), each=nrow(BreastCancer)),
    sample = 1:(2*nrow(BreastCancer))
) %>% pivot_longer(!c(class, sample))
ggplot(tmp) +
    geom_point(aes(x=sample, y=value, color=name, shape=class), 
               alpha=0.5) +
    ylab('Proportion votes for fake class') +
    theme_minimal()

tmp = data.frame(
    pred_real1 = rfs[[1]]$votes[,1],
    pred_real2 = rfs[[2]]$votes[,1],
    pred_real3 = rfs[[3]]$votes[,1],
    pred_real4 = rfs[[4]]$votes[,1],
    class = rep(c('real', 'fake'), each=nrow(BreastCancer)),
    sample = 1:(2*nrow(BreastCancer))
) %>% pivot_longer(!c(class, sample))
ggplot(tmp) +
    geom_point(aes(x=sample, y=value, color=name, shape=class), 
               alpha=0.5) +
    ylab('Proportion votes for fake class') +
    theme_minimal()

aic_fixed = sapply(seq_along(rfs), function(i) {
   clfAIC(y_true[1:nrow(BreastCancer)], y_pred=rfs[[i]]$votes[1:nrow(BreastCancer),], k=i)
})
tmp = as.data.frame(vr2) %>%
    mutate(across(c(AIC, `Corrected AIC`, `Out-of-bag error`), 
                  ~ if(max(.x) == 0) 0 else .x/max(.x))) %>%
    pivot_longer(c(AIC, `Corrected AIC`, `Out-of-bag error`))
tmp2 = data.frame(NA, seq_along(rfs), NA, NA, NA, NA, "AIC_observed_only", aic_fixed/max(aic_fixed))
colnames(tmp2) = colnames(tmp)
tmp = bind_rows(tmp, tmp2)
ggplot(tmp) +
    aes(x=`Number of Variables`, y=value, color=name) +
    geom_line(alpha=0.5) +
    geom_point(alpha=0.5) +
    scale_color_brewer(name="", palette="Dark2") +
    scale_x_continuous(breaks=scales::breaks_pretty(6)) +
    ylab("Relative value") +
    ylim(0, 1) +
    theme_minimal()

5 All data sets

Here I’m going to sweep over the classification data sets available inthe mlbench package and report the results in a table.

I standardize all of the data sets such that the class label is assigned to the column Class.

getdata <- function(...) {
    e = new.env()
    name = data(..., envir = e)[1]
    e[[name]]
}
data_sets = list(
    iris=iris,
    BreastCancer=BreastCancer,
    DNA=getdata("DNA"),
    Glass=getdata("Glass"),
    HouseVotes84=getdata("HouseVotes84"),
    Ionosphere=getdata("Ionosphere"),
#    LetterRecognition=getdata("LetterRecognition"),
    PimaIndiansDiabetes=getdata("PimaIndiansDiabetes"),
    Satellite=getdata("Satellite"),
#    Servo=getdata("Servo"),
#    Shuttle=getdata("Shuttle"),
    Sonar=getdata("Sonar"),
#    Soybean=getdata("Soybean"),
    Vehicle=getdata("Vehicle"),
#    Vowel=getdata("Vowel"),
    Zoo=getdata("Zoo")
)
data_sets = lapply(data_sets, function(x) {
    rn = c('lettr', 'Type', 'diabetes', 'type', 'classes', 'Species')
    if(any(colnames(x) %in% rn)) {
        colnames(x)[colnames(x) %in% rn] = 'Class'
    }
    x[complete.cases(x),]
})
supervised_rfs = cache_rds({
    tmp = lapply(data_sets, function(x) {
        ic(dim(x))
        y = x$Class
        rf = randomForest::randomForest(x = x %>% select(-Class), 
                          y = factor(y), 
                          sampsize=rep(min(table(y)), length(table(y))),
                          strata=factor(y), importance=T, keep.forest=F, ntree=10000)
    
        rf
    })
    names(tmp) = names(data_sets)
    tmp
}, rerun=F, clean=T)

ds_info = bind_rows(lapply(names(data_sets), function(n) {
    x = data_sets[[n]]
    y = x$Class
    rf = supervised_rfs[[n]]
    data.frame(name=n, 
               num_obs=nrow(x),
               num_pred_vars=ncol(x) - 1,
               num_classes=length(table(y)),
               base_accuracy=round(max(table(y)/nrow(x)), digits=3),
               rf_accuracy=round(1 - rf$err.rate[10000, 1], digits=3)
    )
}))
rownames(ds_info) = NULL
#supervised_rfs[[1]]$err.rate[10000,]
reactable(ds_info)
finished = F
unsupervised_rfs1 = cache_rds({
    tmp = lapply(names(data_sets), function(n) {
                     ic(n)
                     usVr(data_sets[[n]] %>% select(-Class))
    })
    names(tmp) = names(data_sets)
    tmp
}, rerun=F, clean=T)

I have 11 data sets here, most of which yield a random forest classification accuracy > 0.9. Only 4 data sets have an rf accuracy < 0.9, with the lowest being the Glass data set with an out-of-bag accuracy of 0.66.

6 Adding noise features

One thing I am curious about is what happens with a diluted clustering signal. One way of testing this is by adding features with little correlation to the class labels or an existing feature.

add_noise_numeric = function(df, n=10, feat=df[,1], r=0.05, prefix="noise.", seed=42) {
    set.seed(seed)
    tmp = do.call('data.frame', lapply(1:n, faux::rnorm_pre, x=feat, r=r))
    colnames(tmp) = paste0(prefix, 1:n)
    cbind(df, tmp)
}
add_noise_categorical = function(df, n=10, feat=df[,1], r=0.05, prefix="noise.", seed=42) {
    set.seed(seed)
    #TODO
}

7 Combined Data Sets

Another way a signal might be diluted is if the data supports multiple sets of clusters. We can simulate this situation by combining two data sets column-wise, randomizing the class labels in one of them such that each sample belongs to two classes, one for each data set (e.g., sample 1 is simultaneously a versicolor and a breast cancer sample).

7.1 Combined Iris and Breast Cancer

An example of what a combined data set might look like:

combine df iris breast cancer
test1 = combineDataSets(iris, BreastCancer)
summary2df(test1)
iris__Sepal.Length iris__Sepal.Width iris__Petal.Length iris__Petal.Width iris__Species BreastCancer__Cl.thickness BreastCancer__Cell.size BreastCancer__Cell.shape BreastCancer__Marg.adhesion BreastCancer__Epith.c.size BreastCancer__Bare.nuclei BreastCancer__Bl.cromatin BreastCancer__Normal.nucleoli BreastCancer__Mitoses BreastCancer__Class
Min. :4.30 Min. :2.00 Min. :1.00 Min. :0.1 setosa :50 Min. : 1.00 Min. : 1.00 Min. : 1.00 Min. : 1.0 Min. : 1.00 Min. : 1.00 Min. : 1.0 Min. : 1.00 Min. :1.00 benign :105
1st Qu.:5.10 1st Qu.:2.80 1st Qu.:1.60 1st Qu.:0.3 versicolor:50 1st Qu.: 1.00 1st Qu.: 1.00 1st Qu.: 1.00 1st Qu.: 1.0 1st Qu.: 2.00 1st Qu.: 1.00 1st Qu.: 2.0 1st Qu.: 1.00 1st Qu.:1.00 malignant: 45
Median :5.80 Median :3.00 Median :4.35 Median :1.3 virginica :50 Median : 3.00 Median : 1.00 Median : 1.00 Median : 1.0 Median : 2.00 Median : 1.00 Median : 3.0 Median : 1.00 Median :1.00 NA
Mean :5.84 Mean :3.06 Mean :3.76 Mean :1.2 NA Mean : 4.15 Mean : 2.86 Mean : 2.88 Mean : 2.5 Mean : 3.14 Mean : 3.17 Mean : 3.2 Mean : 2.43 Mean :1.52 NA
3rd Qu.:6.40 3rd Qu.:3.30 3rd Qu.:5.10 3rd Qu.:1.8 NA 3rd Qu.: 5.00 3rd Qu.: 4.00 3rd Qu.: 4.00 3rd Qu.: 3.0 3rd Qu.: 3.00 3rd Qu.: 5.00 3rd Qu.: 3.0 3rd Qu.: 2.00 3rd Qu.:1.00 NA
Max. :7.90 Max. :4.40 Max. :6.90 Max. :2.5 NA Max. :10.00 Max. :10.00 Max. :10.00 Max. :10.0 Max. :10.00 Max. :10.00 Max. :10.0 Max. :10.00 Max. :9.00 NA
confusionMatrix(factor(test1$iris__Species), factor(test1$BreastCancer__Class))
Confusion matrix.

Ignore the “Observed” and “Predicted” labels as these are reused from my confusion matrix code.

The table above shows that we now have 39 benign-setosa samples, 31 benign-versicolor samples, 11 malignant-setosa samples, etc.

I do not enforce that the class labels across the two data sets are perfectly randomized, so there is some slight imbalances in the combined classes, but in general, they are quite randomized.

irisbc_rf = cache_rds({
    x = test1 
    set.seed(42)
    x_fake = x %>% mutate(across(everything(), ~ sample(.x, size=nrow(x))))
    rf = randomForest::randomForest(x=rbind(x, x_fake), 
                      y =factor(c(rep('real', nrow(x)), rep('fake', nrow(x_fake)))), 
                      importance=T, 
                      keep.forest=T, 
                      ntree=10000)
    rf
}, rerun=F, clean=T)
iris-bc unsupervised importance table
as.data.frame(importance(irisbc_rf)[,3, drop=F]) %>%
    rename(overall=MeanDecreaseAccuracy) %>%
    tibble::rownames_to_column('variable') %>%
    arrange(-overall)
variable overall
BreastCancer__Class 122.55
BreastCancer__Cell.shape 116.04
BreastCancer__Cl.thickness 97.75
BreastCancer__Cell.size 96.68
BreastCancer__Bare.nuclei 94.68
iris__Petal.Length 94.37
BreastCancer__Normal.nucleoli 93.74
BreastCancer__Epith.c.size 91.48
iris__Petal.Width 91.45
iris__Sepal.Length 89.21
iris__Species 89.14
BreastCancer__Marg.adhesion 85.20
BreastCancer__Bl.cromatin 63.53
BreastCancer__Mitoses 51.39
iris__Sepal.Width 38.68

We can create an algorithm that traverses the forest and identifies co-occurence of features together. I suspect that this may distinguish the features that support one set of cluster assignments, and the features that support a second set of cluster assignments.

#' Count the times in a forest that two variables are chosen for adjacent nodes
traverse1 = function(rf, ncores=1) {
    forest = rf$forest
    d = nrow(importance(rf)) # number of variables
    adj = Reduce('+', mclapply(1:rf$ntree, function(k) {
        ar = matrix(0, nrow=d, ncol=d)
        bestvar = forest$bestvar[,k]
        ld = forest$treemap[,1,k]
        rd = forest$treemap[,2,k]
        for(i in 1L:length(bestvar)) {
            if(bestvar[i] == 0) next
            if(bestvar[ld[i]] > 0) 
                ar[bestvar[i], bestvar[ld[i]]] = ar[bestvar[i], bestvar[ld[i]]] + 1
            if(bestvar[rd[i]] > 0) 
                ar[bestvar[i], bestvar[rd[i]]] = ar[bestvar[i], bestvar[rd[i]]] + 1
        }
        ar
    }, mc.cores=ncores))
    colnames(adj) = rownames(adj) = rownames(importance(rf))
    adj = adj + t(adj)

    fact = table(rf$forest$bestvar)
    fact = as.numeric(fact[as.character(1:nrow(adj))])
    fact[is.na(fact)] = 1
    t(adj / fact) / fact
}
#head(randomForest::getTree(irisbc_rf, 1))
#' Count the times in a forest that two variables are chosen within depth $d$
traverse2 = function(rf, depth=3, ncores=1) {
    forest = rf$forest
    d = nrow(importance(rf)) # number of variables
    adj = Reduce('+', mclapply(1:rf$ntree, function(k) {
        ar = matrix(0, nrow=d, ncol=d)
        bestvar = forest$bestvar[,k]
        ld = forest$treemap[,1,k]
        rd = forest$treemap[,2,k]
        for(i in 1L:length(bestvar)) {
            if(bestvar[i] == 0) next
            if(bestvar[ld[i]] > 0) 
                ar[bestvar[i], bestvar[ld[i]]] = ar[bestvar[i], bestvar[ld[i]]] + 1
            if(bestvar[rd[i]] > 0) 
                ar[bestvar[i], bestvar[rd[i]]] = ar[bestvar[i], bestvar[rd[i]]] + 1
        }
        ar
    }, mc.cores=ncores))
    colnames(adj) = rownames(adj) = rownames(importance(rf))
    adj = adj + t(adj)

    fact = table(rf$forest$bestvar)
    fact = as.numeric(fact[as.character(1:nrow(adj))])
    fact[is.na(fact)] = 1
    t(adj / fact) / fact
}
adj = traverse1(irisbc_rf, ncores=1)

tmp = as.data.frame(adj) %>%
    tibble::rownames_to_column('var1') %>%
    pivot_longer(-var1, names_to='var2', values_to='value') %>%
    mutate(var1 = factor(var1, levels=colnames(adj)),
           var2 = factor(var2, levels=colnames(adj)))
p1 = ggplot(tmp) +
    aes(x=var1, y=var2, fill=value) +
    geom_tile() +
#    geom_text(aes(label=round(value, 2))) +
    scale_fill_gradient(name="Feature Pairwise\nCo-occurence", low="white", high="red") +
    xlab("") +
    ylab("") +
    theme_minimal() +
    theme(axis.text.x = element_text(angle=60, vjust=1, hjust=1)) +
    coord_fixed()
tmp2 = adj
tmp2[lower.tri(tmp2, diag=T)] = NA
tmp = as.data.frame(tmp2) %>%
    tibble::rownames_to_column('var1') %>%
    pivot_longer(-var1, names_to='var2', values_to='value') %>%
    mutate(var1 = factor(var1, levels=colnames(adj)),
           var2 = factor(var2, levels=colnames(adj))) %>%
    filter(!is.na(value))
p2 = ggplot(tmp) +
    geom_histogram(aes(x=value), bins=20) + 
    xlab('Pairwise Co-occurence') +
    ylab('Count') +
    theme_minimal()
p1

p2

Ignore the diagonals on the heatmap, as these capture edge cases where sometimes the forest splits on the same variable consecutively.

The exact formula for pairwise co-occurence used here is:

\[ \begin{equation} \textrm{Co-occurence}_{i, j} = \frac{\sum_{t \in T} \sum_{n \in N_{t}} I(i \in E(n))I(j \in E(n))} {f_{i}f_{j}} , \end{equation} \]

where \(i\) and \(j\) are features, \(f_{i}\) is the count of feature label \(i\) over all nodes in a forest, \(T\) is the set of trees in a forest, \(N\) is the set of nodes in a tree, \(I\) is the indicator function, and \(E\) is the set of edges for node \(n\).

co-occurence value table
tmp %>% arrange(-value) %>%
    mutate(value=formatC(value, format="e", digits=3))
var1 var2 value
BreastCancer__Cell.size BreastCancer__Class 6.163e-06
BreastCancer__Normal.nucleoli BreastCancer__Class 5.831e-06
BreastCancer__Bare.nuclei BreastCancer__Class 5.672e-06
BreastCancer__Cell.shape BreastCancer__Class 5.662e-06
iris__Petal.Width iris__Species 5.563e-06
BreastCancer__Marg.adhesion BreastCancer__Class 5.352e-06
iris__Petal.Length iris__Species 5.171e-06
BreastCancer__Cl.thickness BreastCancer__Class 5.117e-06
BreastCancer__Cell.size BreastCancer__Marg.adhesion 5.026e-06
BreastCancer__Cell.size BreastCancer__Epith.c.size 4.996e-06
BreastCancer__Cell.size BreastCancer__Normal.nucleoli 4.984e-06
BreastCancer__Cell.shape BreastCancer__Bare.nuclei 4.974e-06
BreastCancer__Cell.shape BreastCancer__Normal.nucleoli 4.963e-06
BreastCancer__Marg.adhesion BreastCancer__Bare.nuclei 4.910e-06
iris__Sepal.Width iris__Species 4.880e-06
BreastCancer__Bare.nuclei BreastCancer__Normal.nucleoli 4.850e-06
BreastCancer__Mitoses BreastCancer__Class 4.847e-06
BreastCancer__Marg.adhesion BreastCancer__Epith.c.size 4.837e-06
BreastCancer__Epith.c.size BreastCancer__Class 4.818e-06
BreastCancer__Marg.adhesion BreastCancer__Normal.nucleoli 4.800e-06
BreastCancer__Cell.size BreastCancer__Mitoses 4.729e-06
BreastCancer__Epith.c.size BreastCancer__Bare.nuclei 4.721e-06
iris__Sepal.Length iris__Petal.Width 4.703e-06
BreastCancer__Cell.shape BreastCancer__Epith.c.size 4.684e-06
iris__Sepal.Length iris__Petal.Length 4.681e-06
BreastCancer__Cell.shape BreastCancer__Marg.adhesion 4.668e-06
BreastCancer__Marg.adhesion BreastCancer__Bl.cromatin 4.629e-06
iris__Sepal.Length iris__Species 4.613e-06
BreastCancer__Cell.shape BreastCancer__Mitoses 4.582e-06
BreastCancer__Bare.nuclei BreastCancer__Bl.cromatin 4.577e-06
BreastCancer__Epith.c.size BreastCancer__Normal.nucleoli 4.576e-06
BreastCancer__Cl.thickness BreastCancer__Mitoses 4.564e-06
BreastCancer__Cell.size BreastCancer__Cell.shape 4.558e-06
BreastCancer__Cl.thickness BreastCancer__Cell.shape 4.546e-06
iris__Sepal.Width iris__Petal.Width 4.430e-06
iris__Petal.Length iris__Petal.Width 4.418e-06
BreastCancer__Cl.thickness BreastCancer__Bl.cromatin 4.403e-06
BreastCancer__Cl.thickness BreastCancer__Cell.size 4.400e-06
BreastCancer__Cl.thickness BreastCancer__Epith.c.size 4.395e-06
BreastCancer__Epith.c.size BreastCancer__Bl.cromatin 4.388e-06
BreastCancer__Cl.thickness BreastCancer__Bare.nuclei 4.383e-06
BreastCancer__Bare.nuclei BreastCancer__Mitoses 4.375e-06
BreastCancer__Cl.thickness BreastCancer__Normal.nucleoli 4.350e-06
BreastCancer__Epith.c.size BreastCancer__Mitoses 4.336e-06
BreastCancer__Marg.adhesion BreastCancer__Mitoses 4.324e-06
BreastCancer__Bl.cromatin BreastCancer__Normal.nucleoli 4.318e-06
iris__Sepal.Width iris__Petal.Length 4.272e-06
BreastCancer__Bl.cromatin BreastCancer__Class 4.252e-06
BreastCancer__Cell.size BreastCancer__Bare.nuclei 4.251e-06
BreastCancer__Normal.nucleoli BreastCancer__Mitoses 4.248e-06
iris__Sepal.Length iris__Sepal.Width 4.161e-06
BreastCancer__Cell.shape BreastCancer__Bl.cromatin 4.122e-06
BreastCancer__Cell.size BreastCancer__Bl.cromatin 4.114e-06
BreastCancer__Cl.thickness BreastCancer__Marg.adhesion 4.103e-06
BreastCancer__Bl.cromatin BreastCancer__Mitoses 4.062e-06
iris__Sepal.Width BreastCancer__Epith.c.size 4.011e-06
iris__Sepal.Width BreastCancer__Cl.thickness 3.979e-06
iris__Species BreastCancer__Bl.cromatin 3.883e-06
iris__Sepal.Width BreastCancer__Bl.cromatin 3.882e-06
iris__Sepal.Width BreastCancer__Marg.adhesion 3.853e-06
iris__Species BreastCancer__Mitoses 3.779e-06
iris__Sepal.Length BreastCancer__Bl.cromatin 3.773e-06
iris__Sepal.Length BreastCancer__Cl.thickness 3.770e-06
iris__Petal.Width BreastCancer__Bl.cromatin 3.768e-06
iris__Species BreastCancer__Cl.thickness 3.766e-06
iris__Species BreastCancer__Epith.c.size 3.699e-06
iris__Sepal.Length BreastCancer__Epith.c.size 3.678e-06
iris__Sepal.Length BreastCancer__Marg.adhesion 3.659e-06
iris__Petal.Length BreastCancer__Epith.c.size 3.653e-06
iris__Petal.Length BreastCancer__Bl.cromatin 3.611e-06
iris__Petal.Width BreastCancer__Epith.c.size 3.607e-06
iris__Petal.Width BreastCancer__Cl.thickness 3.592e-06
iris__Petal.Length BreastCancer__Cl.thickness 3.586e-06
iris__Species BreastCancer__Cell.shape 3.575e-06
iris__Species BreastCancer__Marg.adhesion 3.557e-06
iris__Sepal.Width BreastCancer__Bare.nuclei 3.556e-06
iris__Petal.Length BreastCancer__Marg.adhesion 3.549e-06
iris__Petal.Length BreastCancer__Normal.nucleoli 3.539e-06
iris__Petal.Length BreastCancer__Bare.nuclei 3.511e-06
iris__Sepal.Length BreastCancer__Mitoses 3.497e-06
iris__Sepal.Length BreastCancer__Normal.nucleoli 3.494e-06
iris__Species BreastCancer__Bare.nuclei 3.486e-06
iris__Sepal.Width BreastCancer__Normal.nucleoli 3.478e-06
iris__Sepal.Length BreastCancer__Bare.nuclei 3.466e-06
iris__Species BreastCancer__Cell.size 3.460e-06
iris__Sepal.Width BreastCancer__Cell.size 3.433e-06
iris__Sepal.Width BreastCancer__Mitoses 3.420e-06
iris__Sepal.Width BreastCancer__Cell.shape 3.418e-06
iris__Sepal.Length BreastCancer__Cell.shape 3.413e-06
iris__Petal.Width BreastCancer__Normal.nucleoli 3.406e-06
iris__Petal.Length BreastCancer__Cell.size 3.396e-06
iris__Sepal.Length BreastCancer__Cell.size 3.363e-06
iris__Petal.Width BreastCancer__Bare.nuclei 3.355e-06
iris__Petal.Width BreastCancer__Cell.size 3.352e-06
iris__Petal.Width BreastCancer__Marg.adhesion 3.346e-06
iris__Petal.Length BreastCancer__Mitoses 3.331e-06
iris__Species BreastCancer__Normal.nucleoli 3.317e-06
iris__Petal.Width BreastCancer__Mitoses 3.271e-06
iris__Petal.Length BreastCancer__Cell.shape 3.232e-06
iris__Petal.Width BreastCancer__Cell.shape 3.219e-06
iris__Sepal.Width BreastCancer__Class 3.154e-06
iris__Species BreastCancer__Class 3.127e-06
iris__Sepal.Length BreastCancer__Class 3.084e-06
iris__Petal.Length BreastCancer__Class 3.060e-06
iris__Petal.Width BreastCancer__Class 2.946e-06

Observations

  • Basic unsupervised random forest algorithm
    • The algorithm by itself seems to still be able to distinguish important and unimportant features, with the Mitoses and Sepal.Width features ranking least in importance (as they are in the original data sets).
    • Several of the breast cancer features seem to dominate the feature importance over the iris features.
      • This may be due to breast cancer having more features than iris
  • With feature co-occurence calculation
    • Co-occurence appears to correspond with the original separate data sets
    • If we do not normalize by the total times features occur in the forest (i.e., remove the denominator in equation (1)), then the class labels have the least co-occurence counts
      • maybe this indicates a bias against choosing categorical variables by unsupervised random forest
    • The histogram shows a bi- or tri-modal distribution, which again supports that the features of different data sets are clustering together
      • Based on the table with ordering, we can see that the comparisons in the smallest mode (greater than 5e-06) are between the BreastCancer__Class and other BreastCancer features (cell.size, normal.nucleoli, bare.nuclei, cell.shape, and marg.adhesion), and one comparison between iris species and iris petal width.
      • Every cross data set comparison (between an iris feature and a breast cancer feature) ranks lower than within data set comparisons, with a cutoff at 4.011e-06
    • The rankings of the co-occurence between features of the same data set appear to be consistent with the general feature importance, i.e., co-occurence values of the iris petal features are higher than co-occurence values of the iris sepal features
  • It may be useful to repeat this analysis without including the true class labels

7.1.1 Co-occurence clustering of features

We can define a distance measure based on the co-occurence between features with:

\[ \begin{equation} Distance_{i, j} = 1 - \frac{\textrm{Co-occurence}_{i, j} }{\max (\textrm{Co-occurence})} . \end{equation} \]

Using hierarchical clustering, we can show that the largest distance is between the two data sets.

ibc.dist = as.dist(1 - adj/max(adj))
#ibc.dist2 = as.dist(-1 * log(adj))
# this second one does not work very well at all, the distances at the leaves are way longer than
# any similarity
plot(hclust(ibc.dist, method = "ward.D2"), hang=-1)
ibc hclust cluster assignments
cutree(hclust(ibc.dist), k=2)
##            iris__Sepal.Length             iris__Sepal.Width 
##                             1                             1 
##            iris__Petal.Length             iris__Petal.Width 
##                             1                             1 
##                 iris__Species    BreastCancer__Cl.thickness 
##                             1                             2 
##       BreastCancer__Cell.size      BreastCancer__Cell.shape 
##                             2                             2 
##   BreastCancer__Marg.adhesion    BreastCancer__Epith.c.size 
##                             2                             2 
##     BreastCancer__Bare.nuclei     BreastCancer__Bl.cromatin 
##                             2                             2 
## BreastCancer__Normal.nucleoli         BreastCancer__Mitoses 
##                             2                             2 
##           BreastCancer__Class 
##                             2

Likewise, optics can identify clusters (along with features that might be removed).

ibc optics other details
#round(sqrt(nrow(adj)))
opt = optics(ibc.dist, minPts=3) # I think minPts is set somewhat arbitrarily - i.e., however many
# features you think should support a given clustering minus 2; in this case, because iris only has
# 5 features (including true class labels, it's detected best when using minPts <= 3
ibc.umap = umap::umap(as.matrix(ibc.dist), input="dist")
tmp = as.data.frame(ibc.umap$layout) %>%
    tibble::rownames_to_column("feature")
opt = extractXi(opt, xi=0.05, minimum=T)
plot(opt)
tmp$cluster = factor(ifelse(opt$cluster == 0, "unclustered", as.character(opt$cluster)))
ggplot(tmp) +
    aes(x=V1, y=V2) +
    geom_point(aes(color=cluster), size=3) +
    ggrepel::geom_text_repel(aes(label=feature)) +
    ggtitle("OPTICS clustering with UMAP mapping") +
    xlab('umap 1') +
    ylab('umap 2') +
    theme_minimal()

7.1.2 Within cluster feature importance

I think there are several ways within cluster feature importance might be described. Two of which I’ve described here:

  1. Use the unsupervised feature importance lists for individual clusters of features
  2. Use the average rank co-occurence between features in the same cluster

7.1.3 AIC

imp = data.frame(importance(irisbc_rf)) %>%
    arrange(desc(MeanDecreaseAccuracy))
rfs = cache_rds({
    lapply(1:(nrow(imp)-1), function(i) {
        vars = rownames(imp)[1:i]    
        usrf(test1[,vars,drop=F], ntree=10000)
    })
})
rfs = c(rfs, list(irisbc_rf))
y_true = rfs[[1]]$y
tmp = bind_rows(lapply(seq_along(rfs), function(i) {
   aic_obs = clfAIC(y_true[1:(length(y_true)/2)], 
                      y_pred=rfs[[i]]$votes[1:(length(y_true)/2),], k=i)
   aic = clfAIC(y_true, y_pred=rfs[[i]]$votes, k=i)
   err = rfs[[i]]$err.rate[10000, 1]
   vars = nrow(importance(rfs[[i]]))
   data.frame(AIC=aic, AIC_obs=aic_obs, error=err, nvars=vars)
})) %>% 
    mutate(across(!nvars, ~ .x / max(.x))) %>%
    pivot_longer(!c(nvars)) %>%
    group_by(name) %>%
    mutate(is.min = value == min(value))

ggplot(tmp) +
    aes(x=nvars, y=value, color=name) +
    geom_line(alpha=0.5) +
    geom_point(aes(shape=is.min), alpha=0.5) +
    scale_color_brewer(name="", palette="Dark2") +
    scale_x_continuous(name="Number of variables", breaks=scales::breaks_pretty(6),
                       sec.axis = sec_axis(~ . * 1, breaks=1:nrow(imp), labels=rownames(imp))) +
    ylim(0, 1) +
    ylab("Relative value") +
    theme_minimal() +
    theme(axis.text.x.top = element_text(angle=60, vjust=0, hjust=0))

clus = as.data.frame(ibc.umap$layout)
clus$cluster = opt$cluster
#clus
add_rfs = cache_rds({
    lapply(1:2, function(i) {
        vars = rownames(clus)[clus$cluster == i]    
        usrf(test1[,vars,drop=F], ntree=10000, seed=41)
})}, rerun=F, clean=T)

tmp2 = bind_rows(lapply(seq_along(add_rfs), function(i) {
   rf = add_rfs[[i]]
   vars = nrow(importance(rf))
   aic_obs = clfAIC(y_true[1:(length(y_true)/2)], 
                      y_pred=rf$votes[1:(length(y_true)/2),], k=vars)
   aic = clfAIC(y_true, y_pred=rf$votes, k=vars)
   err = rf$err.rate[10000, 1]
   data.frame(AIC=aic, AIC_obs=aic_obs, error=err, nvars=vars)
}))
tmp = bind_rows(lapply(seq_along(rfs), function(i) {
   vars = nrow(importance(rfs[[i]]))
   aic_obs = clfAIC(y_true[1:(length(y_true)/2)], 
                      y_pred=rfs[[i]]$votes[1:(length(y_true)/2),], k=vars)
   aic = clfAIC(y_true, y_pred=rfs[[i]]$votes, k=vars)
   err = rfs[[i]]$err.rate[10000, 1]
   data.frame(AIC=aic, AIC_obs=aic_obs, error=err, nvars=vars)
}))

tmp2$AIC = tmp2$AIC / max(tmp$AIC)
tmp2$AIC_obs = tmp2$AIC_obs / max(tmp$AIC_obs)
tmp2$error = tmp2$error / max(tmp$error)

tmp = tmp %>% 
    mutate(across(!nvars, ~ .x / max(.x))) %>%
    pivot_longer(!c(nvars)) %>%
    group_by(name) %>%
    mutate(is.min = value == min(value))
tmp2 = tmp2 %>% 
    pivot_longer(!c(nvars)) %>%
    mutate(is.min=F) %>%
    filter(value <= 1)

ggplot(tmp) +
    geom_line(aes(x=nvars, y=value, color=name), alpha=0.5) +
    geom_point(aes(x=nvars, y=value, color=name, shape=is.min), alpha=0.5) +
    scale_color_brewer(name="", palette="Dark2") +
    scale_x_continuous(name="Number of variables", breaks=scales::breaks_pretty(6),
                       sec.axis = sec_axis(~ . * 1, breaks=1:nrow(imp), labels=rownames(imp))) +
    ylim(0, 1) +
    ylab("Relative value") +
    theme_minimal() +
    geom_point(data=tmp2, mapping=aes(x=nvars, y=value, color=name), shape=3, size=3) +
    theme(axis.text.x.top = element_text(angle=60, vjust=0, hjust=0))

LS0tCnRpdGxlOiAiVGVzdCBmZWF0dXJlIHNlbGVjdGlvbiBhbmQgaW1wb3J0YW5jZSB1c2luZyB1bnN1cGVydmlzZWQgcmFuZG9tRm9yZXN0IgphdXRob3I6ICJZaSBDaGVuIgpkYXRlOiAiYHIgU3lzLkRhdGUoKWAiCm91dHB1dDogCiAgICBodG1sX2RvY3VtZW50OgogICAgICAgIHRoZW1lOiBwYXBlcgogICAgICAgIGhpZ2hsaWdodDogdGFuZ28KICAgICAgICB0b2M6IHRydWUKICAgICAgICB0b2NfZGVwdGg6IDMKICAgICAgICB0b2NfZmxvYXQ6CiAgICAgICAgICAgIGNvbGxhcHNlZDogdHJ1ZQogICAgICAgIG51bWJlcl9zZWN0aW9uczogdHJ1ZQogICAgICAgIGNvZGVfZG93bmxvYWQ6IHRydWUKICAgICAgICBkZl9wcmludDoga2FibGUKICAgICAgICBjb2RlX2ZvbGRpbmc6IGhpZGUKICAgICAgICBtb2RlOiBzZWxmY29udGFpbmVkCi0tLQo8c2NyaXB0IHR5cGU9InRleHQveC1tYXRoamF4LWNvbmZpZyI+Ck1hdGhKYXguSHViLkNvbmZpZyh7CiAgVGVYOiB7IGVxdWF0aW9uTnVtYmVyczogeyBhdXRvTnVtYmVyOiAiQU1TIiB9IH0KfSk7Cjwvc2NyaXB0Pgo8c3R5bGUgdHlwZT0idGV4dC9jc3MiPgpib2R5eyBmb250LWZhbWlseTogc2VyaWY7IGZvbnQtc2l6ZTogMTFwdDsgfQpoMSB7IGZvbnQtc2l6ZTogMjRwdDsgfQpoMiB7IGZvbnQtc2l6ZTogMjBwdDsgfQpoMyB7IGZvbnQtc2l6ZTogMTZwdDsgfQpzdW1tYXJ5IHsgY3Vyc29yOiBwb2ludGVyOyB9CnAgeyBtYXgtd2lkdGg6IDYwMHB4OyB9CmNhcHRpb24sIC5jYXB0aW9uIHsgY29sb3I6ICM2NjY2NjY7IH0KZGV0YWlscyB7cGFkZGluZy10b3A6MTVweDsgcGFkZGluZy1ib3R0b206MTVweDt9CmVtYmVkIHsgd2lkdGg6IDc1MHB4OyBoZWlnaHQ6IDYwMHB4OyB9Ci50b2MtY29udGVudHsgbWF4LXdpZHRoOiA3NTBweDsgfQo8L3N0eWxlPgpgYGB7ciBzZXR1cCwgZWNobz1GLCB3YXJuaW5nPUYsIHNldHVwPVR9CmtuaXRyOjpvcHRzX2tuaXQkc2V0KHVwbG9hZC5mdW4gPSBrbml0cjo6aW1hZ2VfdXJpKQprbml0cjo6b3B0c19jaHVuayRzZXQoZmlnLmFsaWduPSJjZW50ZXIiLCByZXN1bHRzPSJob2xkIiwgY2FjaGUucGF0aD0iY2FjaGUvIiwgZGV2PSJwbmciLAogICAgICAgICAgICAgICAgICAgICAgZmlnLndpZHRoPTYuNSwgZmlnLmhlaWdodD02LjUpClIudXRpbHM6OnNldE9wdGlvbigiZGlnaXRzIiwgNCkKc3RkZXJycCA9IGZ1bmN0aW9uKC4uLikgeyAKICAgIGRvdHMgPSBsaXN0KC4uLikKICAgIGlmKGFueShzYXBwbHkoZG90cywgY2xhc3MpID09ICdjaGFyYWN0ZXInKSkgewogICAgICAgIHdyaXRlKHBhc3RlKC4uLiksIHN0ZGVycigpKSAKICAgIH0gZWxzZSB7CiAgICAgICAgd3JpdGUocGFzdGUwKGNhcHR1cmUub3V0cHV0KC4uLikpLCBzdGRlcnIoKSkgCiAgICB9Cn0KaWMgPSBzdGRlcnJwCmtuaXRyOjprbml0X2hvb2tzJHNldCh0aW1laXQgPSBsb2NhbCh7CiAgICBub3cgPC0gTlVMTAogICAgZnVuY3Rpb24oYmVmb3JlLCBvcHRpb25zKSB7CiAgICAgICAgaWYoYmVmb3JlKSB7CiAgICAgICAgICAgIG5vdyA8PC0gU3lzLnRpbWUoKQogICAgICAgIH0gZWxzZSB7CiAgICAgICAgICAgIHJlcyA8LSBkaWZmdGltZShTeXMudGltZSgpLCBub3cpCiAgICAgICAgICAgIG5vdyA8LSBOVUxMCiAgICAgICAgICAgIHN0ZGVycnAocGFzdGUoJ1xuJywKICAgICAgICAgICAgICAgIHN0cmluZ3I6OnN0cl9wYWQob3B0aW9ucyRsYWJlbCwgMjAsIHNpZGU9InJpZ2h0IiksIAogICAgICAgICAgICAgICAgc3RyaW5ncjo6c3RyX3BhZChyb3VuZChhcy5udW1lcmljKHJlcyksIGRpZ2l0cz0yKSwgOSksCiAgICAgICAgICAgICAgICB1bml0cyhyZXMpKSkKICAgICAgICB9CiAgICB9fSksCiAgICBzdW1tYXJ5ID0gewogICAgICAgIGZ1bmN0aW9uKGJlZm9yZSwgb3B0aW9ucykgewogICAgICAgICAgICBpZihiZWZvcmUpIHsKICAgICAgICAgICAgICAgIHJldHVybihhc2lzX291dHB1dChwYXN0ZTAoIjxkZXRhaWxzPjxzdW1tYXJ5PiIsIAogICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgIGdzdWIoJ18nLCAnICcsIG9wdGlvbnMkbGFiZWwpLCAiPC9zdW1tYXJ5PlxuIikpKQogICAgICAgICAgICB9IGVsc2UgewogICAgICAgICAgICAgICAgcmV0dXJuKGFzaXNfb3V0cHV0KCI8L2RldGFpbHM+XG4iKSkKICAgICAgICAgICAgfQogICAgICAgIH0KICAgIH0KKQprbml0cjo6b3B0c19jaHVuayRzZXQodGltZWl0PVQpCmlzLmh0bWwgPSBrbml0cjo6aXNfaHRtbF9vdXRwdXQoKQpgYGAKYGBge3IgbG9hZExpYnJhcmllcywgZWNobz1GLCBtZXNzYWdlPUYsIHdhcm5pbmc9RiwgbG9hZExpYnJhcmllcz1UfQpsaWJyYXJ5KHhmdW4pCmxpYnJhcnkoeWZ1bikKbGlicmFyeShrbml0cikKbGlicmFyeShyZWFjdGFibGUpCmxpYnJhcnkodGlkeXZlcnNlKQpsaWJyYXJ5KHBhdGNod29yaykKbGlicmFyeShwYXJhbGxlbCkKbGlicmFyeSh2YXJSZWR1Y3QpCmxpYnJhcnkobWxiZW5jaCkKbGlicmFyeShkYnNjYW4pCmBgYAoKIyBJbnRyb2R1Y3Rpb24KCkhlcmUsIEkgd3JpdGUgY29kZSB0aGF0IHRlc3RzIHRoZSB3aGV0aGVyIGZvcndhcmQgZmVhdHVyZSBzZWxlY3Rpb24gbWFrZXMgc2Vuc2UgaW4gdGhlIGNvbnRleHQgb2YKdW5zdXBlcnZpc2VkIHJhbmRvbUZvcmVzdC4KCiMgVmFyUmVkdWN0CgpgYGB7ciBydW5WYXJSZWR1Y3RGdW5jdGlvbiwgY2xhc3Muc291cmNlPSdmb2xkLXNob3cnfQp1c1ZyID0gZnVuY3Rpb24oeCwgc2VlZD00MikgewogICAgc2V0LnNlZWQoc2VlZCkKICAgIHhfZmFrZSA9IHggJT4lIG11dGF0ZShhY3Jvc3MoZXZlcnl0aGluZygpLCB+IHNhbXBsZSgueCwgc2l6ZT1ucm93KHgpKSkpCiAgICB2YXJSZWR1Y3QocHJlZGljdG9yX3ZhcnM9cmJpbmQoeCwgeF9mYWtlKSwKICAgICAgICAgICAgICAgIHJlc3BvbnNlX3Zhcj1mYWN0b3IoYyhyZXAoJ3JlYWwnLCBucm93KHgpKSwgcmVwKCdmYWtlJywgbnJvdyh4X2Zha2UpKSkpLAogICAgICAgICAgICAgICAgdmFyUmVkdWN0X21ldGhvZD0nZm9yd2FyZFNlbGVjdCcsCiAgICAgICAgICAgICAgICBhbGdvPSdyYW5kb21Gb3Jlc3QnLAogICAgICAgICAgICAgICAgc2VsZWN0X21ldGhvZD0nZWxib3dfYW5kX2dhcCcsCiAgICAgICAgICAgICAgICB0cmFjZT1GLAojICAgICAgICAgICAgICAgIG51bV9qb2JzPTEsCiAgICAgICAgICAgICAgICBzZWVkPTQyKQp9CmBgYApgYGB7ciB1c3JmX2Z1bmN9CnVzcmYgPSBmdW5jdGlvbih4LCBzZWVkPTQyLCBudHJlZT0xMDAwKSB7CiAgICBzZXQuc2VlZChzZWVkKQogICAgeF9mYWtlID0geCAlPiUgbXV0YXRlKGFjcm9zcyhldmVyeXRoaW5nKCksIH4gc2FtcGxlKC54LCBzaXplPW5yb3coeCkpKSkKICAgIHJmID0gcmFuZG9tRm9yZXN0OjpyYW5kb21Gb3Jlc3QoeD1yYmluZCh4LCB4X2Zha2UpLAogICAgICAgICAgICAgICAgICAgICAgeT1mYWN0b3IoYyhyZXAoJ3JlYWwnLCBucm93KHgpKSwgcmVwKCdmYWtlJywgbnJvdyh4X2Zha2UpKSkpLAogICAgICAgICAgICAgICAgICAgICAgaW1wb3J0YW5jZT1ULAogICAgICAgICAgICAgICAgICAgICAga2VlcC5mb3Jlc3Q9RiwKICAgICAgICAgICAgICAgICAgICAgIG50cmVlPW50cmVlCiAgICAgICAgICAgICAgICAgICAgICApCiAgICByZgp9CmBgYApgYGB7ciBwbG90VnJGdW5jMX0KdmFyaW1wY29tcF9wbG90ID0gZnVuY3Rpb24oLi4uKSB7CiAgICBkb3RzID0gbGlzdCguLi4pCiAgICBpZihpcy5udWxsKG5hbWVzKGRvdHMpKSkgewogICAgICAgIG5hbWVzKGRvdHMpID0gdW5saXN0KGxhcHBseShzdWJzdGl0dXRlKGxpc3QoLi4uKSlbLTFdLCBkZXBhcnNlKSkKICAgIH0KICAgIGtzID0gc2FwcGx5KGRvdHMsIGZ1bmN0aW9uKHgpIG5yb3coaW1wb3J0YW5jZSh4KSkpCiAgICB0bXAgPSBiaW5kX3Jvd3MobGFwcGx5KHNlcV9hbG9uZyhkb3RzKSwgZnVuY3Rpb24oaSkgewogICAgICAgIHggPSBkb3RzW1tpXV0KICAgICAgICB0bXAgPSBpbXBvcnRhbmNlKHgpICU+JSAKICAgICAgICAgICAgdGliYmxlOjpyb3duYW1lc190b19jb2x1bW4oJ3ZhcmlhYmxlJykgJT4lIAogICAgICAgICAgICBtdXRhdGUocnVuPW5hbWVzKGRvdHMpW2ldKSAlPiUKICAgICAgICAgICAgbXV0YXRlKHZpbXBfcmFuaz1yYW5rKC1vdmVyYWxsKSkKICAgICAgICBpZihrc1tpXSA+IG1pbihrcykpIHsKICAgICAgICAgICAgdG1wJHZpbXBfcmFuayA9IHRtcCR2aW1wX3JhbmsgLSAxCiAgICAgICAgfQogICAgICAgIHRtcAogICAgfSkpCiAgICB0bXAyID0gdG1wICU+JSBncm91cF9ieSh2YXJpYWJsZSkgJT4lCiAgICAgICAgc3VtbWFyaXplKHZpbXBfcmFuaz1tZWFuKHZpbXBfcmFuaykpICU+JQogICAgICAgIGFycmFuZ2UoLXZpbXBfcmFuaykgJT4lCiAgICAgICAgcHVsbCh2YXJpYWJsZSkKICAgIHRtcCR2YXJpYWJsZSA9IGZhY3Rvcih0bXAkdmFyaWFibGUsIGxldmVscz10bXAyKQogICAgZ2dwbG90KHRtcCkgKwogICAgICAgIGFlcyh4PXZpbXBfcmFuaywgeT12YXJpYWJsZSkgKwogICAgICAgIGdlb21fc2VnbWVudChhZXMoeGVuZD0wLCBncm91cD1ydW4pLCBjb2xvcj0iZ3JleTY5IiwgbGluZXR5cGU9ImRhc2hlZCIsCiAgICAgICAgICAgICAgICAgICAgIHBvc2l0aW9uPXBvc2l0aW9uX2RvZGdlKHdpZHRoPTAuNSkpICsKICAgICAgICBnZW9tX3BvaW50KGFlcyhjb2xvcj1ydW4pLCBwb3NpdGlvbj1wb3NpdGlvbl9kb2RnZSh3aWR0aD0wLjUpKSArCiAgICAgICAgc2NhbGVfY29sb3JfYnJld2VyKG5hbWU9IiIsIHBhbGV0dGU9IkRhcmsyIikgKwogICAgICAgIHhsYWIoInJhbmsoIHZhcmlhYmxlIGltcG9ydGFuY2UgKSIpICsKICAgICAgICB5bGFiKCIiKSArCiAgICAgICAgc2NhbGVfeF9jb250aW51b3VzKGJyZWFrcz1zY2FsZXM6OmJyZWFrc19wcmV0dHkoKSkgKwogICAgICAgIGd1aWRlcyhjb2xvdXI9Z3VpZGVfbGVnZW5kKHJldmVyc2U9VCwgcG9zaXRpb249ImJvdHRvbSIpKSArCiAgICAgICAgdGhlbWVfbWluaW1hbCgpCn0KYGBgCmBgYHtyIHBsb3RWckZ1bmMyfQp2aW1wX3NwZWFybWFuX3Bsb3QgPSBmdW5jdGlvbiguLi4pIHsKICAgIGRvdHMgPSBsaXN0KC4uLikKICAgIGlmKGlzLm51bGwobmFtZXMoZG90cykpKSB7CiAgICAgICAgbmFtZXMoZG90cykgPSB1bmxpc3QobGFwcGx5KHN1YnN0aXR1dGUobGlzdCguLi4pKVstMV0sIGRlcGFyc2UpKQogICAgfQogICAgdmltcHMgPSBsYXBwbHkobmFtZXMoZG90cyksIGZ1bmN0aW9uKG5hbWUpIHsKICAgICAgICB4ID0gZG90c1tbbmFtZV1dCiAgICAgICAgdG1wID0gaW1wb3J0YW5jZSh4KSAlPiUgCiAgICAgICAgICAgIHRpYmJsZTo6cm93bmFtZXNfdG9fY29sdW1uKCd2YXJpYWJsZScpICU+JQogICAgICAgICAgICBzZWxlY3QoIWltcG9ydGFudCkKICAgICAgICBjb2xuYW1lcyh0bXApW2NvbG5hbWVzKHRtcCkgPT0gJ292ZXJhbGwnXSA9IG5hbWUKICAgICAgICB0bXAKICAgIH0pCiAgICB0bXAgPSByZWR1Y2UodmltcHMsIGlubmVyX2pvaW4sIGJ5PSd2YXJpYWJsZScpICU+JQogICAgICAgIHRpYmJsZTo6Y29sdW1uX3RvX3Jvd25hbWVzKCd2YXJpYWJsZScpCiAgICB0bXAgPSBjb3IodG1wLCBtZXRob2Q9J3NwZWFybWFuJykKICAgIHRtcCA9IGFzLmRhdGEuZnJhbWUodG1wKSAlPiUKICAgICAgICB0aWJibGU6OnJvd25hbWVzX3RvX2NvbHVtbigndmFyMScpICU+JQogICAgICAgIHBpdm90X2xvbmdlcigtdmFyMSwgbmFtZXNfdG89J3ZhcjInLCB2YWx1ZXNfdG89J3ZhbHVlJykgJT4lCiAgICAgICAgbXV0YXRlKHZhcjEgPSBmYWN0b3IodmFyMSwgbGV2ZWxzPWNvbG5hbWVzKHRtcCkpLAogICAgICAgICAgICAgICB2YXIyID0gZmFjdG9yKHZhcjIsIGxldmVscz1jb2xuYW1lcyh0bXApKSkKICAgIGdncGxvdCh0bXApICsKICAgICAgICBhZXMoeD12YXIxLCB5PXZhcjIsIGZpbGw9dmFsdWUpICsKICAgICAgICBnZW9tX3RpbGUoKSArCiAgICAgICAgZ2VvbV90ZXh0KGFlcyhsYWJlbD1yb3VuZCh2YWx1ZSwgMikpKSArCiAgICAgICAgc2NhbGVfZmlsbF9ncmFkaWVudDIobmFtZT0iU3BlYXJtYW5cbmNvcnJlbGF0aW9uIiwgbWlkcG9pbnQ9MCwgbG93PSJibHVlIiwgCiAgICAgICAgICAgICAgICAgICAgICAgICAgICAgbWlkPSJ3aGl0ZSIsIGhpZ2g9InJlZCIsIGxpbWl0cz1jKC0xLCAxKSkgKwogICAgICAgIHhsYWIoIiIpICsKICAgICAgICB5bGFiKCIiKSArCiAgICAgICAgdGhlbWVfbWluaW1hbCgpICsKICAgICAgICB0aGVtZShheGlzLnRleHQueCA9IGVsZW1lbnRfdGV4dChhbmdsZT02MCwgdmp1c3Q9MSwgaGp1c3Q9MSkpICsKICAgICAgICBjb29yZF9maXhlZCgpCn0KYGBgCmBgYHtyIHN1bW1hcnkyZGZfZnVuY30Kc3VtbWFyeTJkZiA9IGZ1bmN0aW9uKHgpIHsKICAgIGRhdGEuZnJhbWUodW5jbGFzcyhzdW1tYXJ5KHgpKSwgY2hlY2submFtZXMgPSBGQUxTRSwgc3RyaW5nc0FzRmFjdG9ycyA9IEZBTFNFKSAlPiUKICAgICAgICBgcm93bmFtZXM8LWAoIE5VTEwgKQp9CmBgYApgYGB7ciBjb21iaW5lRGF0YVNldEZ1bmN9CmNvbWJpbmVEYXRhU2V0cyA9IGZ1bmN0aW9uKC4uLiwgc2VlZD00MikgewogICAgc2V0LnNlZWQoc2VlZCkKICAgIGRmcyA9IGxpc3QoLi4uKQogICAgaWYoaXMubnVsbChuYW1lcyhkZnMpKSkgewogICAgICAgIG5hbWVzKGRmcykgPSB1bmxpc3QobGFwcGx5KHN1YnN0aXR1dGUobGlzdCguLi4pKVstMV0sIGRlcGFyc2UpKQogICAgfQogICAgbiA9IG1pbihzYXBwbHkoZGZzLCBucm93KSkKICAgIGJpbmRfY29scyhsYXBwbHkobmFtZXMoZGZzKSwgZnVuY3Rpb24obmFtZSkgewogICAgICAgIGRmID0gZGZzW1tuYW1lXV0KICAgICAgICBjb2xuYW1lcyhkZikgPSBwYXN0ZShuYW1lLCBjb2xuYW1lcyhkZiksIHNlcD0nX18nKQogICAgICAgIGlmKG5yb3coZGYpID09IG4pIHsgcmV0dXJuKGRmKSB9CiMgICAgICAgIGsgPSBkZiAlPiUgcHVsbChlbmRzX3dpdGgoJ0NsYXNzJykpICU+JSB1bmlxdWUoKSAlPiUgbGVuZ3RoKCkKICAgICAgICBkZiAlPiUjIGdyb3VwX2J5KGFjcm9zcyhlbmRzX3dpdGgoJ0NsYXNzJykpKSAlPiUKICAgICAgICAgICAgc2xpY2Vfc2FtcGxlKG49bikgCiAgICB9KSkKfQpgYGAKCiMgSXJpcyBkYXRhIHNldAoKYGBge3IgaXJpc19zdW1tYXJ5LCBzdW1tYXJ5PVR9CnN1bW1hcnkyZGYoaXJpcykKYGBgCgpgYGB7ciBzdXBlcnZpc2VkX3J1bl9pcmlzLCBzdW1tYXJ5PVR9CnZyMSA9IGNhY2hlX3Jkcyh7CiAgICB2YXJSZWR1Y3QocHJlZGljdG9yX3ZhcnM9aXJpc1ssMTo0XSwKICAgICAgICAgICAgICAgIHJlc3BvbnNlX3Zhcj1mYWN0b3IoaXJpcyRTcGVjaWVzKSwKICAgICAgICAgICAgICAgIHZhclJlZHVjdF9tZXRob2Q9J2ZvcndhcmRTZWxlY3QnLAogICAgICAgICAgICAgICAgYWxnbz0ncmFuZG9tRm9yZXN0JywKICAgICAgICAgICAgICAgIHRyYWNlPUYsCiAgICAgICAgICAgICAgICBudW1fam9icz00LAogICAgICAgICAgICAgICAgc2VlZD00MikKfSwgcmVydW49RiwgY2xlYW49VCkKdnIxJGJlc3RfaXRlcgp2cjEkZXZhbF92ZWMKdnIxJG51bV92YXJzX3ZlYwppbXBvcnRhbmNlKHZyMSkKYGBgCgpgYGB7ciB1bnN1cGVydmlzZWRfcnVuX3dpdGhfdHJ1ZV9sYWJlbHMsIHN1bW1hcnk9VH0KdnIyID0gY2FjaGVfcmRzKHsKICAgIHVzVnIoaXJpcykKfSwgcmVydW49RiwgY2xlYW49VCkKdnIyJGJlc3RfaXRlcgp2cjIkZXZhbF92ZWMKdnIyJG51bV92YXJzX3ZlYwppbXBvcnRhbmNlKHZyMikKYGBgCgpgYGB7ciB1bnN1cGVydmlzZWRfcnVuX3dpdGhvdXRfdHJ1ZV9sYWJlbHMsIHN1bW1hcnk9VH0KdnIzID0gY2FjaGVfcmRzKHsKICAgIHVzVnIoaXJpc1ssMTo0XSkKfSwgcmVydW49RiwgY2xlYW49VCkKdnIzJGJlc3RfaXRlcgp2cjMkZXZhbF92ZWMKdnIzJG51bV92YXJzX3ZlYwppbXBvcnRhbmNlKHZyMykKYGBgCgpgYGB7ciBwbG90X2lyaXMsIGZpZy53aWR0aD0xMH0KcDEgPSB2YXJpbXBjb21wX3Bsb3Qoc3VwZXJ2aXNlZD12cjEsIHVuc3VwZXJ2aXNlZF93dGw9dnIyLCB1bnN1cGVydmlzZWRfd290bD12cjMpCnAyID0gdmltcF9zcGVhcm1hbl9wbG90KHN1cGVydmlzZWQ9dnIxLCB1bnN1cGVydmlzZWRfd3RsPXZyMiwgdW5zdXBlcnZpc2VkX3dvdGw9dnIzKQpwMSArIHAyCmBgYApgYGB7ciBwbG90X3ZyX2Z1bmN9CnBsb3RfdnIgPSBmdW5jdGlvbih2cikgewogICAgdG1wID0gYXMuZGF0YS5mcmFtZSh2cikgJT4lCiAgICAgICAgbXV0YXRlKGFjcm9zcyhjKEFJQywgYENvcnJlY3RlZCBBSUNgLCBgT3V0LW9mLWJhZyBlcnJvcmApLCAKICAgICAgICAgICAgICAgICAgICAgIH4gaWYobWF4KC54KSA9PSAwKSAwIGVsc2UgLngvbWF4KC54KSkpICU+JQogICAgICAgIHBpdm90X2xvbmdlcihjKEFJQywgYENvcnJlY3RlZCBBSUNgLCBgT3V0LW9mLWJhZyBlcnJvcmApKQogICAgZ2dwbG90KHRtcCkgKwogICAgICAgIGFlcyh4PWBOdW1iZXIgb2YgVmFyaWFibGVzYCwgeT12YWx1ZSwgY29sb3I9bmFtZSkgKwogICAgICAgIGdlb21fbGluZShhbHBoYT0wLjUpICsKICAgICAgICBnZW9tX3BvaW50KGFscGhhPTAuNSkgKwogICAgICAgIHNjYWxlX2NvbG9yX2JyZXdlcihuYW1lPSIiLCBwYWxldHRlPSJEYXJrMiIpICsKICAgICAgICBzY2FsZV94X2NvbnRpbnVvdXMoYnJlYWtzPXNjYWxlczo6YnJlYWtzX3ByZXR0eSg2KSkgKwogICAgICAgIHlsYWIoIlJlbGF0aXZlIHZhbHVlIikgKwogICAgICAgIHRoZW1lX21pbmltYWwoKQp9CmBgYApgYGB7ciBwbG90X2lyaXMyfQpwbG90X3ZyKHZyMikgLyBwbG90X3ZyKHZyMykgKyBwbG90X2xheW91dChndWlkZXM9J2NvbGxlY3QnKQpgYGAKCgo8bWFyaz5PYnNlcnZhdGlvbnM8L21hcms+CgotIEluY2x1ZGluZyB0aGUgdHJ1ZSBjbGFzcyBsYWJlbHMsIHRoZSB0cnVlIGNsYXNzIGxhYmVscyBhcmUgc2VsZWN0ZWQgYXMgdGhlIG1vc3QgaW1wb3J0YW50IGZlYXR1cmUKICB3aGVuIGRvaW5nIHVuc3VwZXJ2aXNlZCBmZWF0dXJlIHNlbGVjdGlvbgotIFRoZSBvcmRlcmluZyBvZiB0aGUgZmVhdHVyZXMgaXMgdGhlIGV4YWN0IHNhbWUgd2hldGhlciBpbmNsdWRpbmcgdHJ1ZSBsYWJlbHMgb3Igbm90IGNvbXBhcmVkIHRvCiAgdXNpbmcgc3VwZXJ2aXNlZCByYW5kb21Gb3Jlc3QKICAtIEkgdGVzdGVkIHRoaXMgd2l0aCBhIGRpZmZlcmVudCBzZWVkIGJlZm9yZSwgYW5kIHRoZXJlIHdhcyBvbmUgc3dhcCAodGhlIGBQZXRhbGAgZmVhdHVyZXMpLAogICAgaW5kaWNhdGluZyB0aGVyZSBpcyBzb21lIHN0b2NoYXN0aWNpdHkgaW4gaXQKCiMjIENsb3NlciBsb29rIGF0IEFJQyBpbiBpcmlzCgpgYGB7ciBpcmlzX2FpY30KaW1wID0gaW1wb3J0YW5jZSh2cjMpCnJmcyA9IGNhY2hlX3Jkcyh7CiAgICBsYXBwbHkoMTpucm93KGltcCksIGZ1bmN0aW9uKGkpIHsKICAgICAgICB2YXJzID0gcm93bmFtZXMoaW1wKVsxOmldICAgIAogICAgICAgIHVzcmYoaXJpc1ssdmFycyxkcm9wPUZdLCBudHJlZT01MDAwKQogICAgfSkKfSwgcmVydW49RiwgY2xlYW49VCkKeV90cnVlID0gcmZzW1szXV0keQpgYGAKCmBgYHtyIGlyaXNfYWljX3Bsb3QyfQp0bXAgPSBkYXRhLmZyYW1lKAogICAgcHJlZF9yZWFsMSA9IHJmc1tbMV1dJHZvdGVzWywxXSwKICAgIHByZWRfcmVhbDIgPSByZnNbWzJdXSR2b3Rlc1ssMV0sCiAgICBwcmVkX3JlYWwzID0gcmZzW1szXV0kdm90ZXNbLDFdLAogICAgcHJlZF9yZWFsNCA9IHJmc1tbNF1dJHZvdGVzWywxXSwKICAgIGNsYXNzID0gcmVwKGMoJ3JlYWwnLCAnZmFrZScpLCBlYWNoPW5yb3coaXJpcykpLAogICAgc2FtcGxlID0gMTooMipucm93KGlyaXMpKQopICU+JSBwaXZvdF9sb25nZXIoIWMoY2xhc3MsIHNhbXBsZSkpCmdncGxvdCh0bXApICsKICAgIGdlb21fcG9pbnQoYWVzKHg9c2FtcGxlLCB5PXZhbHVlLCBjb2xvcj1uYW1lLCBzaGFwZT1jbGFzcyksIAogICAgICAgICAgICAgICBhbHBoYT0wLjUpICsKICAgIHlsYWIoJ1Byb3BvcnRpb24gdm90ZXMgZm9yIGZha2UgY2xhc3MnKSArCiAgICB0aGVtZV9taW5pbWFsKCkKYGBgCgpgYGB7ciBpcmlzX2FpY19vYnNlcnZlZF9vbmx5fQphaWNfZml4ZWQgPSBzYXBwbHkoc2VxX2Fsb25nKHJmcyksIGZ1bmN0aW9uKGkpIHsKICAgY2xmQUlDKHlfdHJ1ZVsxOm5yb3coaXJpcyldLCB5X3ByZWQ9cmZzW1tpXV0kdm90ZXNbMTpucm93KGlyaXMpLF0sIGs9aSkKfSkKdG1wID0gYXMuZGF0YS5mcmFtZSh2cjMpICU+JQogICAgbXV0YXRlKGFjcm9zcyhjKEFJQywgYENvcnJlY3RlZCBBSUNgLCBgT3V0LW9mLWJhZyBlcnJvcmApLCAKICAgICAgICAgICAgICAgICAgfiBpZihtYXgoLngpID09IDApIDAgZWxzZSAueC9tYXgoLngpKSkgJT4lCiAgICBwaXZvdF9sb25nZXIoYyhBSUMsIGBDb3JyZWN0ZWQgQUlDYCwgYE91dC1vZi1iYWcgZXJyb3JgKSkKdG1wMiA9IGRhdGEuZnJhbWUoTkEsIHNlcV9hbG9uZyhyZnMpLCBOQSwgTkEsIE5BLCBOQSwgIkFJQ19vYnNlcnZlZF9vbmx5IiwgYWljX2ZpeGVkL21heChhaWNfZml4ZWQpKQpjb2xuYW1lcyh0bXAyKSA9IGNvbG5hbWVzKHRtcCkKdG1wID0gYmluZF9yb3dzKHRtcCwgdG1wMikKZ2dwbG90KHRtcCkgKwogICAgYWVzKHg9YE51bWJlciBvZiBWYXJpYWJsZXNgLCB5PXZhbHVlLCBjb2xvcj1uYW1lKSArCiAgICBnZW9tX2xpbmUoYWxwaGE9MC41KSArCiAgICBnZW9tX3BvaW50KGFscGhhPTAuNSkgKwogICAgc2NhbGVfY29sb3JfYnJld2VyKG5hbWU9IiIsIHBhbGV0dGU9IkRhcmsyIikgKwogICAgc2NhbGVfeF9jb250aW51b3VzKGJyZWFrcz1zY2FsZXM6OmJyZWFrc19wcmV0dHkoNikpICsKICAgIHlsaW0oMCwgMSkgKwogICAgeWxhYigiUmVsYXRpdmUgdmFsdWUiKSArCiAgICB0aGVtZV9taW5pbWFsKCkKYGBgCgoKCgojIEJyZWFzdCBDYW5jZXIKCmBgYHtyIGJyZWFzdF9jYW5jZXJfc3VtbWFyeSwgc3VtbWFyeT1UfQpkYXRhKCJCcmVhc3RDYW5jZXIiLCBwYWNrYWdlID0gIm1sYmVuY2giKQpCcmVhc3RDYW5jZXIgPSBCcmVhc3RDYW5jZXIgJT4lIAogICAgc2VsZWN0KCFJZCkgJT4lCiAgICBtdXRhdGUoYWNyb3NzKCFDbGFzcywgYXMubnVtZXJpYykpICU+JQogICAgZmlsdGVyKCFpcy5uYShCYXJlLm51Y2xlaSkpCnN1bW1hcnkyZGYoQnJlYXN0Q2FuY2VyKQpgYGAKCmBgYHtyIHN1cGVydmlzZWRfcnVuX2JyZWFzdF9jYW5jZXIsIHN1bW1hcnk9VH0KdnIxID0gY2FjaGVfcmRzKHsKICAgIHZhclJlZHVjdChwcmVkaWN0b3JfdmFycz1CcmVhc3RDYW5jZXIgJT4lIHNlbGVjdCgtQ2xhc3MpLAogICAgICAgICAgICAgICAgcmVzcG9uc2VfdmFyPWZhY3RvcihCcmVhc3RDYW5jZXIkQ2xhc3MpLAogICAgICAgICAgICAgICAgdmFyUmVkdWN0X21ldGhvZD0nZm9yd2FyZFNlbGVjdCcsCiAgICAgICAgICAgICAgICBhbGdvPSdyYW5kb21Gb3Jlc3QnLAogICAgICAgICAgICAgICAgdHJhY2U9RiwKICAgICAgICAgICAgICAgIHByZXByb2Nlc3M9RiwKICAgICAgICAgICAgICAgIHNlZWQ9NDIpCn0sIHJlcnVuPUYsIGNsZWFuPVQpCnZyMSRiZXN0X2l0ZXIKdnIxJGV2YWxfdmVjCnZyMSRudW1fdmFyc192ZWMKaW1wb3J0YW5jZSh2cjEpCmBgYAoKYGBge3IgdW5zdXBlcnZpc2VkX3J1bl93aXRoX3RydWVfbGFiZWxzX2JyZWFzdF9jYW5jZXIsIHN1bW1hcnk9VH0KdnIyID0gY2FjaGVfcmRzKHsKICAgIHVzVnIoQnJlYXN0Q2FuY2VyKQp9LCByZXJ1bj1GLCBjbGVhbj1UKQp2cjIkYmVzdF9pdGVyCnZyMiRldmFsX3ZlYwp2cjIkbnVtX3ZhcnNfdmVjCmltcG9ydGFuY2UodnIyKQpgYGAKCmBgYHtyIHVuc3VwZXJ2aXNlZF9ydW5fd2l0aG91dF90cnVlX2xhYmVsc19icmVhc3RfY2FuY2VyLCBzdW1tYXJ5PVR9CnZyMyA9IGNhY2hlX3Jkcyh7CiAgICB1c1ZyKEJyZWFzdENhbmNlclssMToobmNvbChCcmVhc3RDYW5jZXIpLTEpXSkKfSwgcmVydW49RiwgY2xlYW49VCkKdnIzJGJlc3RfaXRlcgp2cjMkZXZhbF92ZWMKdnIzJG51bV92YXJzX3ZlYwppbXBvcnRhbmNlKHZyMykKYGBgCgpgYGB7ciBwbG90X2JjLCBmaWcud2lkdGg9MTB9CnAxID0gdmFyaW1wY29tcF9wbG90KHN1cGVydmlzZWQ9dnIxLCB1bnN1cGVydmlzZWRfd3RsPXZyMiwgdW5zdXBlcnZpc2VkX3dvdGw9dnIzKQpwMiA9IHZpbXBfc3BlYXJtYW5fcGxvdChzdXBlcnZpc2VkPXZyMSwgdW5zdXBlcnZpc2VkX3d0bD12cjIsIHVuc3VwZXJ2aXNlZF93b3RsPXZyMykKcDEgKyBwMgpgYGAKYGBge3IgcGxvdF9iYzJ9CnBsb3RfdnIodnIyKSAvIHBsb3RfdnIodnIzKSArIHBsb3RfbGF5b3V0KGd1aWRlcz0nY29sbGVjdCcpCmBgYAoKIyMgQ2xvc2VyIGxvb2sgYXQgQUlDIGluIGJyZWFzdCBjYW5jZXIKCmBgYHtyIGJyZWFzdF9jYW5jZXJfYWljfQppbXAgPSBpbXBvcnRhbmNlKHZyMikKcmZzID0gY2FjaGVfcmRzKHsKICAgIGxhcHBseSgxOm5yb3coaW1wKSwgZnVuY3Rpb24oaSkgewogICAgICAgIHZhcnMgPSByb3duYW1lcyhpbXApWzE6aV0gICAgCiAgICAgICAgdXNyZihCcmVhc3RDYW5jZXJbLHZhcnMsZHJvcD1GXSwgbnRyZWU9NTAwMCkKICAgIH0pCn0sIHJlcnVuPUYsIGNsZWFuPVQpCnlfdHJ1ZSA9IHJmc1tbM11dJHkKYGBgCgpgYGB7ciBicmVhc3RfY2FuY2VyX2FpY19wbG90MX0KdG1wID0gZGF0YS5mcmFtZSgKICAgIHByZWRfcmVhbDMgPSByZnNbWzNdXSR2b3Rlc1ssMV0sCiAgICBwcmVkX3JlYWw0ID0gcmZzW1s0XV0kdm90ZXNbLDFdLAogICAgY2xhc3MgPSByZXAoYygncmVhbCcsICdmYWtlJyksIGVhY2g9bnJvdyhCcmVhc3RDYW5jZXIpKSwKICAgIHNhbXBsZSA9IDE6KDIqbnJvdyhCcmVhc3RDYW5jZXIpKQopICU+JSBwaXZvdF9sb25nZXIoIWMoY2xhc3MsIHNhbXBsZSkpCmdncGxvdCh0bXApICsKICAgIGdlb21fcG9pbnQoYWVzKHg9c2FtcGxlLCB5PXZhbHVlLCBjb2xvcj1uYW1lLCBzaGFwZT1jbGFzcyksIAogICAgICAgICAgICAgICBhbHBoYT0wLjUpICsKICAgIHlsYWIoJ1Byb3BvcnRpb24gdm90ZXMgZm9yIGZha2UgY2xhc3MnKSArCiAgICB0aGVtZV9taW5pbWFsKCkKYGBgCmBgYHtyIGJyZWFzdF9jYW5jZXJfYWljX3Bsb3QyfQp0bXAgPSBkYXRhLmZyYW1lKAogICAgcHJlZF9yZWFsMSA9IHJmc1tbMV1dJHZvdGVzWywxXSwKICAgIHByZWRfcmVhbDIgPSByZnNbWzJdXSR2b3Rlc1ssMV0sCiAgICBwcmVkX3JlYWwzID0gcmZzW1szXV0kdm90ZXNbLDFdLAogICAgcHJlZF9yZWFsNCA9IHJmc1tbNF1dJHZvdGVzWywxXSwKICAgIGNsYXNzID0gcmVwKGMoJ3JlYWwnLCAnZmFrZScpLCBlYWNoPW5yb3coQnJlYXN0Q2FuY2VyKSksCiAgICBzYW1wbGUgPSAxOigyKm5yb3coQnJlYXN0Q2FuY2VyKSkKKSAlPiUgcGl2b3RfbG9uZ2VyKCFjKGNsYXNzLCBzYW1wbGUpKQpnZ3Bsb3QodG1wKSArCiAgICBnZW9tX3BvaW50KGFlcyh4PXNhbXBsZSwgeT12YWx1ZSwgY29sb3I9bmFtZSwgc2hhcGU9Y2xhc3MpLCAKICAgICAgICAgICAgICAgYWxwaGE9MC41KSArCiAgICB5bGFiKCdQcm9wb3J0aW9uIHZvdGVzIGZvciBmYWtlIGNsYXNzJykgKwogICAgdGhlbWVfbWluaW1hbCgpCmBgYAoKYGBge3IgYnJlYXN0X2NhbmNlcl9haWNfb2JzZXJ2ZWRfb25seX0KYWljX2ZpeGVkID0gc2FwcGx5KHNlcV9hbG9uZyhyZnMpLCBmdW5jdGlvbihpKSB7CiAgIGNsZkFJQyh5X3RydWVbMTpucm93KEJyZWFzdENhbmNlcildLCB5X3ByZWQ9cmZzW1tpXV0kdm90ZXNbMTpucm93KEJyZWFzdENhbmNlciksXSwgaz1pKQp9KQp0bXAgPSBhcy5kYXRhLmZyYW1lKHZyMikgJT4lCiAgICBtdXRhdGUoYWNyb3NzKGMoQUlDLCBgQ29ycmVjdGVkIEFJQ2AsIGBPdXQtb2YtYmFnIGVycm9yYCksIAogICAgICAgICAgICAgICAgICB+IGlmKG1heCgueCkgPT0gMCkgMCBlbHNlIC54L21heCgueCkpKSAlPiUKICAgIHBpdm90X2xvbmdlcihjKEFJQywgYENvcnJlY3RlZCBBSUNgLCBgT3V0LW9mLWJhZyBlcnJvcmApKQp0bXAyID0gZGF0YS5mcmFtZShOQSwgc2VxX2Fsb25nKHJmcyksIE5BLCBOQSwgTkEsIE5BLCAiQUlDX29ic2VydmVkX29ubHkiLCBhaWNfZml4ZWQvbWF4KGFpY19maXhlZCkpCmNvbG5hbWVzKHRtcDIpID0gY29sbmFtZXModG1wKQp0bXAgPSBiaW5kX3Jvd3ModG1wLCB0bXAyKQpnZ3Bsb3QodG1wKSArCiAgICBhZXMoeD1gTnVtYmVyIG9mIFZhcmlhYmxlc2AsIHk9dmFsdWUsIGNvbG9yPW5hbWUpICsKICAgIGdlb21fbGluZShhbHBoYT0wLjUpICsKICAgIGdlb21fcG9pbnQoYWxwaGE9MC41KSArCiAgICBzY2FsZV9jb2xvcl9icmV3ZXIobmFtZT0iIiwgcGFsZXR0ZT0iRGFyazIiKSArCiAgICBzY2FsZV94X2NvbnRpbnVvdXMoYnJlYWtzPXNjYWxlczo6YnJlYWtzX3ByZXR0eSg2KSkgKwogICAgeWxhYigiUmVsYXRpdmUgdmFsdWUiKSArCiAgICB5bGltKDAsIDEpICsKICAgIHRoZW1lX21pbmltYWwoKQpgYGAKCgojIEFsbCBkYXRhIHNldHMKCkhlcmUgSSdtIGdvaW5nIHRvIHN3ZWVwIG92ZXIgdGhlIGNsYXNzaWZpY2F0aW9uIGRhdGEgc2V0cyBhdmFpbGFibGUgaW50aGUgYG1sYmVuY2hgIHBhY2thZ2UgYW5kCnJlcG9ydCB0aGUgcmVzdWx0cyBpbiBhIHRhYmxlLgoKSSBzdGFuZGFyZGl6ZSBhbGwgb2YgdGhlIGRhdGEgc2V0cyBzdWNoIHRoYXQgdGhlIGNsYXNzIGxhYmVsIGlzIGFzc2lnbmVkIHRvIHRoZSBjb2x1bW4gYENsYXNzYC4KCmBgYHtyIGJ1aWxkX2FsbF9kYXRhX3NldHN9CmdldGRhdGEgPC0gZnVuY3Rpb24oLi4uKSB7CiAgICBlID0gbmV3LmVudigpCiAgICBuYW1lID0gZGF0YSguLi4sIGVudmlyID0gZSlbMV0KICAgIGVbW25hbWVdXQp9CmRhdGFfc2V0cyA9IGxpc3QoCiAgICBpcmlzPWlyaXMsCiAgICBCcmVhc3RDYW5jZXI9QnJlYXN0Q2FuY2VyLAogICAgRE5BPWdldGRhdGEoIkROQSIpLAogICAgR2xhc3M9Z2V0ZGF0YSgiR2xhc3MiKSwKICAgIEhvdXNlVm90ZXM4ND1nZXRkYXRhKCJIb3VzZVZvdGVzODQiKSwKICAgIElvbm9zcGhlcmU9Z2V0ZGF0YSgiSW9ub3NwaGVyZSIpLAojICAgIExldHRlclJlY29nbml0aW9uPWdldGRhdGEoIkxldHRlclJlY29nbml0aW9uIiksCiAgICBQaW1hSW5kaWFuc0RpYWJldGVzPWdldGRhdGEoIlBpbWFJbmRpYW5zRGlhYmV0ZXMiKSwKICAgIFNhdGVsbGl0ZT1nZXRkYXRhKCJTYXRlbGxpdGUiKSwKIyAgICBTZXJ2bz1nZXRkYXRhKCJTZXJ2byIpLAojICAgIFNodXR0bGU9Z2V0ZGF0YSgiU2h1dHRsZSIpLAogICAgU29uYXI9Z2V0ZGF0YSgiU29uYXIiKSwKIyAgICBTb3liZWFuPWdldGRhdGEoIlNveWJlYW4iKSwKICAgIFZlaGljbGU9Z2V0ZGF0YSgiVmVoaWNsZSIpLAojICAgIFZvd2VsPWdldGRhdGEoIlZvd2VsIiksCiAgICBab289Z2V0ZGF0YSgiWm9vIikKKQpkYXRhX3NldHMgPSBsYXBwbHkoZGF0YV9zZXRzLCBmdW5jdGlvbih4KSB7CiAgICBybiA9IGMoJ2xldHRyJywgJ1R5cGUnLCAnZGlhYmV0ZXMnLCAndHlwZScsICdjbGFzc2VzJywgJ1NwZWNpZXMnKQogICAgaWYoYW55KGNvbG5hbWVzKHgpICVpbiUgcm4pKSB7CiAgICAgICAgY29sbmFtZXMoeClbY29sbmFtZXMoeCkgJWluJSBybl0gPSAnQ2xhc3MnCiAgICB9CiAgICB4W2NvbXBsZXRlLmNhc2VzKHgpLF0KfSkKYGBgCmBgYHtyIGNoYXJhY3Rlcml6ZV9hbGxfZGF0YV9zZXRzLCBldmFsPVR9CnN1cGVydmlzZWRfcmZzID0gY2FjaGVfcmRzKHsKICAgIHRtcCA9IGxhcHBseShkYXRhX3NldHMsIGZ1bmN0aW9uKHgpIHsKICAgICAgICBpYyhkaW0oeCkpCiAgICAgICAgeSA9IHgkQ2xhc3MKICAgICAgICByZiA9IHJhbmRvbUZvcmVzdDo6cmFuZG9tRm9yZXN0KHggPSB4ICU+JSBzZWxlY3QoLUNsYXNzKSwgCiAgICAgICAgICAgICAgICAgICAgICAgICAgeSA9IGZhY3Rvcih5KSwgCiAgICAgICAgICAgICAgICAgICAgICAgICAgc2FtcHNpemU9cmVwKG1pbih0YWJsZSh5KSksIGxlbmd0aCh0YWJsZSh5KSkpLAogICAgICAgICAgICAgICAgICAgICAgICAgIHN0cmF0YT1mYWN0b3IoeSksIGltcG9ydGFuY2U9VCwga2VlcC5mb3Jlc3Q9RiwgbnRyZWU9MTAwMDApCiAgICAKICAgICAgICByZgogICAgfSkKICAgIG5hbWVzKHRtcCkgPSBuYW1lcyhkYXRhX3NldHMpCiAgICB0bXAKfSwgcmVydW49RiwgY2xlYW49VCkKCmRzX2luZm8gPSBiaW5kX3Jvd3MobGFwcGx5KG5hbWVzKGRhdGFfc2V0cyksIGZ1bmN0aW9uKG4pIHsKICAgIHggPSBkYXRhX3NldHNbW25dXQogICAgeSA9IHgkQ2xhc3MKICAgIHJmID0gc3VwZXJ2aXNlZF9yZnNbW25dXQogICAgZGF0YS5mcmFtZShuYW1lPW4sIAogICAgICAgICAgICAgICBudW1fb2JzPW5yb3coeCksCiAgICAgICAgICAgICAgIG51bV9wcmVkX3ZhcnM9bmNvbCh4KSAtIDEsCiAgICAgICAgICAgICAgIG51bV9jbGFzc2VzPWxlbmd0aCh0YWJsZSh5KSksCiAgICAgICAgICAgICAgIGJhc2VfYWNjdXJhY3k9cm91bmQobWF4KHRhYmxlKHkpL25yb3coeCkpLCBkaWdpdHM9MyksCiAgICAgICAgICAgICAgIHJmX2FjY3VyYWN5PXJvdW5kKDEgLSByZiRlcnIucmF0ZVsxMDAwMCwgMV0sIGRpZ2l0cz0zKQogICAgKQp9KSkKcm93bmFtZXMoZHNfaW5mbykgPSBOVUxMCiNzdXBlcnZpc2VkX3Jmc1tbMV1dJGVyci5yYXRlWzEwMDAwLF0KcmVhY3RhYmxlKGRzX2luZm8pCmBgYApgYGB7ciBzZXRGaW5pc2hlZH0KZmluaXNoZWQgPSBGCmBgYApgYGB7ciB1bnN1cGVydmlzZWRfd290bF9hbGxfZGF0YV9zZXRzLCBldmFsPWZpbmlzaGVkfQp1bnN1cGVydmlzZWRfcmZzMSA9IGNhY2hlX3Jkcyh7CiAgICB0bXAgPSBsYXBwbHkobmFtZXMoZGF0YV9zZXRzKSwgZnVuY3Rpb24obikgewogICAgICAgICAgICAgICAgICAgICBpYyhuKQogICAgICAgICAgICAgICAgICAgICB1c1ZyKGRhdGFfc2V0c1tbbl1dICU+JSBzZWxlY3QoLUNsYXNzKSkKICAgIH0pCiAgICBuYW1lcyh0bXApID0gbmFtZXMoZGF0YV9zZXRzKQogICAgdG1wCn0sIHJlcnVuPUYsIGNsZWFuPVQpCmBgYApgYGB7ciBjb21wX3VzX3N1cF9hbGxfZGF0YV9zZXRzLCBldmFsPWZpbmlzaGVkfQoKYGBgCgpJIGhhdmUgMTEgZGF0YSBzZXRzIGhlcmUsIG1vc3Qgb2Ygd2hpY2ggeWllbGQgYSByYW5kb20gZm9yZXN0IGNsYXNzaWZpY2F0aW9uIGFjY3VyYWN5ID4gMC45LiBPbmx5IDQgCmRhdGEgc2V0cyBoYXZlIGFuIHJmIGFjY3VyYWN5IDwgMC45LCB3aXRoIHRoZSBsb3dlc3QgYmVpbmcgdGhlIEdsYXNzIGRhdGEgc2V0IHdpdGggYW4gb3V0LW9mLWJhZwphY2N1cmFjeSBvZiAwLjY2LgoKIyBBZGRpbmcgbm9pc2UgZmVhdHVyZXMKCk9uZSB0aGluZyBJIGFtIGN1cmlvdXMgYWJvdXQgaXMgd2hhdCBoYXBwZW5zIHdpdGggYSBkaWx1dGVkIGNsdXN0ZXJpbmcgc2lnbmFsLiBPbmUgd2F5IG9mIHRlc3RpbmcKdGhpcyBpcyBieSBhZGRpbmcgZmVhdHVyZXMgd2l0aCBsaXR0bGUgY29ycmVsYXRpb24gdG8gdGhlIGNsYXNzIGxhYmVscyBvciBhbiBleGlzdGluZyBmZWF0dXJlLgoKYGBge3Igbm9pc2VfZmVhdF9mdW5jfQphZGRfbm9pc2VfbnVtZXJpYyA9IGZ1bmN0aW9uKGRmLCBuPTEwLCBmZWF0PWRmWywxXSwgcj0wLjA1LCBwcmVmaXg9Im5vaXNlLiIsIHNlZWQ9NDIpIHsKICAgIHNldC5zZWVkKHNlZWQpCiAgICB0bXAgPSBkby5jYWxsKCdkYXRhLmZyYW1lJywgbGFwcGx5KDE6biwgZmF1eDo6cm5vcm1fcHJlLCB4PWZlYXQsIHI9cikpCiAgICBjb2xuYW1lcyh0bXApID0gcGFzdGUwKHByZWZpeCwgMTpuKQogICAgY2JpbmQoZGYsIHRtcCkKfQphZGRfbm9pc2VfY2F0ZWdvcmljYWwgPSBmdW5jdGlvbihkZiwgbj0xMCwgZmVhdD1kZlssMV0sIHI9MC4wNSwgcHJlZml4PSJub2lzZS4iLCBzZWVkPTQyKSB7CiAgICBzZXQuc2VlZChzZWVkKQogICAgI1RPRE8KfQpgYGAKCiMgQ29tYmluZWQgRGF0YSBTZXRzCgpBbm90aGVyIHdheSBhIHNpZ25hbCBtaWdodCBiZSBkaWx1dGVkIGlzIGlmIHRoZSBkYXRhIHN1cHBvcnRzIG11bHRpcGxlIHNldHMgb2YgY2x1c3RlcnMuIFdlCmNhbiBzaW11bGF0ZSB0aGlzIHNpdHVhdGlvbiBieSBjb21iaW5pbmcgdHdvIGRhdGEgc2V0cyBjb2x1bW4td2lzZSwgcmFuZG9taXppbmcgdGhlIGNsYXNzIGxhYmVscyBpbgpvbmUgb2YgdGhlbSBzdWNoIHRoYXQgZWFjaCBzYW1wbGUgYmVsb25ncyB0byB0d28gY2xhc3Nlcywgb25lIGZvciBlYWNoIGRhdGEgc2V0IChlLmcuLCBzYW1wbGUgMSBpcwpzaW11bHRhbmVvdXNseSBhIHZlcnNpY29sb3IgYW5kIGEgYnJlYXN0IGNhbmNlciBzYW1wbGUpLgoKIyMgQ29tYmluZWQgSXJpcyBhbmQgQnJlYXN0IENhbmNlcgoKQW4gZXhhbXBsZSBvZiB3aGF0IGEgY29tYmluZWQgZGF0YSBzZXQgbWlnaHQgbG9vayBsaWtlOgoKYGBge3IgY29tYmluZV9kZl9pcmlzX2JyZWFzdF9jYW5jZXIsIHN1bW1hcnk9VH0KdGVzdDEgPSBjb21iaW5lRGF0YVNldHMoaXJpcywgQnJlYXN0Q2FuY2VyKQpzdW1tYXJ5MmRmKHRlc3QxKQpgYGAKYGBge3IgY29tYmluZV9kZl9pcmlzX2JyZWFzdF9jYW5jZXJfY2xhc3NfbGFiZWxfY29uZnVzaW9uX21hdHJpeH0KY29uZnVzaW9uTWF0cml4KGZhY3Rvcih0ZXN0MSRpcmlzX19TcGVjaWVzKSwgZmFjdG9yKHRlc3QxJEJyZWFzdENhbmNlcl9fQ2xhc3MpKQpgYGAKCklnbm9yZSB0aGUgIk9ic2VydmVkIiBhbmQgIlByZWRpY3RlZCIgbGFiZWxzIGFzIHRoZXNlIGFyZSByZXVzZWQgZnJvbSBteSBjb25mdXNpb24gbWF0cml4IGNvZGUuCgpUaGUgdGFibGUgYWJvdmUgc2hvd3MgdGhhdCB3ZSBub3cgaGF2ZSAzOSBiZW5pZ24tc2V0b3NhIHNhbXBsZXMsIDMxIGJlbmlnbi12ZXJzaWNvbG9yIHNhbXBsZXMsIDExCm1hbGlnbmFudC1zZXRvc2Egc2FtcGxlcywgZXRjLiAKCkkgZG8gbm90IGVuZm9yY2UgdGhhdCB0aGUgY2xhc3MgbGFiZWxzIGFjcm9zcyB0aGUgdHdvIGRhdGEgc2V0cyBhcmUgcGVyZmVjdGx5IHJhbmRvbWl6ZWQsIHNvIHRoZXJlCmlzIHNvbWUgc2xpZ2h0IGltYmFsYW5jZXMgaW4gdGhlIGNvbWJpbmVkIGNsYXNzZXMsIGJ1dCBpbiBnZW5lcmFsLCB0aGV5IGFyZSBxdWl0ZSByYW5kb21pemVkLgoKYGBge3IgdXNfdnJfaXJpc19icmVhc3RfY2FuY2VyfQppcmlzYmNfcmYgPSBjYWNoZV9yZHMoewogICAgeCA9IHRlc3QxIAogICAgc2V0LnNlZWQoNDIpCiAgICB4X2Zha2UgPSB4ICU+JSBtdXRhdGUoYWNyb3NzKGV2ZXJ5dGhpbmcoKSwgfiBzYW1wbGUoLngsIHNpemU9bnJvdyh4KSkpKQogICAgcmYgPSByYW5kb21Gb3Jlc3Q6OnJhbmRvbUZvcmVzdCh4PXJiaW5kKHgsIHhfZmFrZSksIAogICAgICAgICAgICAgICAgICAgICAgeSA9ZmFjdG9yKGMocmVwKCdyZWFsJywgbnJvdyh4KSksIHJlcCgnZmFrZScsIG5yb3coeF9mYWtlKSkpKSwgCiAgICAgICAgICAgICAgICAgICAgICBpbXBvcnRhbmNlPVQsIAogICAgICAgICAgICAgICAgICAgICAga2VlcC5mb3Jlc3Q9VCwgCiAgICAgICAgICAgICAgICAgICAgICBudHJlZT0xMDAwMCkKICAgIHJmCn0sIHJlcnVuPUYsIGNsZWFuPVQpCmBgYApgYGB7ciBpcmlzLWJjX3Vuc3VwZXJ2aXNlZF9pbXBvcnRhbmNlX3RhYmxlLCBzdW1tYXJ5PVR9CmFzLmRhdGEuZnJhbWUoaW1wb3J0YW5jZShpcmlzYmNfcmYpWywzLCBkcm9wPUZdKSAlPiUKICAgIHJlbmFtZShvdmVyYWxsPU1lYW5EZWNyZWFzZUFjY3VyYWN5KSAlPiUKICAgIHRpYmJsZTo6cm93bmFtZXNfdG9fY29sdW1uKCd2YXJpYWJsZScpICU+JQogICAgYXJyYW5nZSgtb3ZlcmFsbCkKYGBgCgpXZSBjYW4gY3JlYXRlIGFuIGFsZ29yaXRobSB0aGF0IHRyYXZlcnNlcyB0aGUgZm9yZXN0IGFuZCBpZGVudGlmaWVzIGNvLW9jY3VyZW5jZSBvZiBmZWF0dXJlcwp0b2dldGhlci4gSSBzdXNwZWN0IHRoYXQgdGhpcyBtYXkgZGlzdGluZ3Vpc2ggdGhlIGZlYXR1cmVzIHRoYXQgc3VwcG9ydCBvbmUgc2V0IG9mIGNsdXN0ZXIKYXNzaWdubWVudHMsIGFuZCB0aGUgZmVhdHVyZXMgdGhhdCBzdXBwb3J0IGEgc2Vjb25kIHNldCBvZiBjbHVzdGVyIGFzc2lnbm1lbnRzLgoKYGBge3IgdHJhdmVyc2VGb3Jlc3RGdW5jMX0KIycgQ291bnQgdGhlIHRpbWVzIGluIGEgZm9yZXN0IHRoYXQgdHdvIHZhcmlhYmxlcyBhcmUgY2hvc2VuIGZvciBhZGphY2VudCBub2Rlcwp0cmF2ZXJzZTEgPSBmdW5jdGlvbihyZiwgbmNvcmVzPTEpIHsKICAgIGZvcmVzdCA9IHJmJGZvcmVzdAogICAgZCA9IG5yb3coaW1wb3J0YW5jZShyZikpICMgbnVtYmVyIG9mIHZhcmlhYmxlcwogICAgYWRqID0gUmVkdWNlKCcrJywgbWNsYXBwbHkoMTpyZiRudHJlZSwgZnVuY3Rpb24oaykgewogICAgICAgIGFyID0gbWF0cml4KDAsIG5yb3c9ZCwgbmNvbD1kKQogICAgICAgIGJlc3R2YXIgPSBmb3Jlc3QkYmVzdHZhclssa10KICAgICAgICBsZCA9IGZvcmVzdCR0cmVlbWFwWywxLGtdCiAgICAgICAgcmQgPSBmb3Jlc3QkdHJlZW1hcFssMixrXQogICAgICAgIGZvcihpIGluIDFMOmxlbmd0aChiZXN0dmFyKSkgewogICAgICAgICAgICBpZihiZXN0dmFyW2ldID09IDApIG5leHQKICAgICAgICAgICAgaWYoYmVzdHZhcltsZFtpXV0gPiAwKSAKICAgICAgICAgICAgICAgIGFyW2Jlc3R2YXJbaV0sIGJlc3R2YXJbbGRbaV1dXSA9IGFyW2Jlc3R2YXJbaV0sIGJlc3R2YXJbbGRbaV1dXSArIDEKICAgICAgICAgICAgaWYoYmVzdHZhcltyZFtpXV0gPiAwKSAKICAgICAgICAgICAgICAgIGFyW2Jlc3R2YXJbaV0sIGJlc3R2YXJbcmRbaV1dXSA9IGFyW2Jlc3R2YXJbaV0sIGJlc3R2YXJbcmRbaV1dXSArIDEKICAgICAgICB9CiAgICAgICAgYXIKICAgIH0sIG1jLmNvcmVzPW5jb3JlcykpCiAgICBjb2xuYW1lcyhhZGopID0gcm93bmFtZXMoYWRqKSA9IHJvd25hbWVzKGltcG9ydGFuY2UocmYpKQogICAgYWRqID0gYWRqICsgdChhZGopCgogICAgZmFjdCA9IHRhYmxlKHJmJGZvcmVzdCRiZXN0dmFyKQogICAgZmFjdCA9IGFzLm51bWVyaWMoZmFjdFthcy5jaGFyYWN0ZXIoMTpucm93KGFkaikpXSkKICAgIGZhY3RbaXMubmEoZmFjdCldID0gMQogICAgdChhZGogLyBmYWN0KSAvIGZhY3QKfQojaGVhZChyYW5kb21Gb3Jlc3Q6OmdldFRyZWUoaXJpc2JjX3JmLCAxKSkKYGBgCmBgYHtyIHRyYXZlcnNlRm9yZXN0RnVuYzJ9CiMnIENvdW50IHRoZSB0aW1lcyBpbiBhIGZvcmVzdCB0aGF0IHR3byB2YXJpYWJsZXMgYXJlIGNob3NlbiB3aXRoaW4gZGVwdGggJGQkCnRyYXZlcnNlMiA9IGZ1bmN0aW9uKHJmLCBkZXB0aD0zLCBuY29yZXM9MSkgewogICAgZm9yZXN0ID0gcmYkZm9yZXN0CiAgICBkID0gbnJvdyhpbXBvcnRhbmNlKHJmKSkgIyBudW1iZXIgb2YgdmFyaWFibGVzCiAgICBhZGogPSBSZWR1Y2UoJysnLCBtY2xhcHBseSgxOnJmJG50cmVlLCBmdW5jdGlvbihrKSB7CiAgICAgICAgYXIgPSBtYXRyaXgoMCwgbnJvdz1kLCBuY29sPWQpCiAgICAgICAgYmVzdHZhciA9IGZvcmVzdCRiZXN0dmFyWyxrXQogICAgICAgIGxkID0gZm9yZXN0JHRyZWVtYXBbLDEsa10KICAgICAgICByZCA9IGZvcmVzdCR0cmVlbWFwWywyLGtdCiAgICAgICAgZm9yKGkgaW4gMUw6bGVuZ3RoKGJlc3R2YXIpKSB7CiAgICAgICAgICAgIGlmKGJlc3R2YXJbaV0gPT0gMCkgbmV4dAogICAgICAgICAgICBpZihiZXN0dmFyW2xkW2ldXSA+IDApIAogICAgICAgICAgICAgICAgYXJbYmVzdHZhcltpXSwgYmVzdHZhcltsZFtpXV1dID0gYXJbYmVzdHZhcltpXSwgYmVzdHZhcltsZFtpXV1dICsgMQogICAgICAgICAgICBpZihiZXN0dmFyW3JkW2ldXSA+IDApIAogICAgICAgICAgICAgICAgYXJbYmVzdHZhcltpXSwgYmVzdHZhcltyZFtpXV1dID0gYXJbYmVzdHZhcltpXSwgYmVzdHZhcltyZFtpXV1dICsgMQogICAgICAgIH0KICAgICAgICBhcgogICAgfSwgbWMuY29yZXM9bmNvcmVzKSkKICAgIGNvbG5hbWVzKGFkaikgPSByb3duYW1lcyhhZGopID0gcm93bmFtZXMoaW1wb3J0YW5jZShyZikpCiAgICBhZGogPSBhZGogKyB0KGFkaikKCiAgICBmYWN0ID0gdGFibGUocmYkZm9yZXN0JGJlc3R2YXIpCiAgICBmYWN0ID0gYXMubnVtZXJpYyhmYWN0W2FzLmNoYXJhY3RlcigxOm5yb3coYWRqKSldKQogICAgZmFjdFtpcy5uYShmYWN0KV0gPSAxCiAgICB0KGFkaiAvIGZhY3QpIC8gZmFjdAp9CmBgYApgYGB7ciB0cmF2ZXJzZTFfaXJpc2JjLCBmaWcuaGVpZ2h0PTR9CmFkaiA9IHRyYXZlcnNlMShpcmlzYmNfcmYsIG5jb3Jlcz0xKQoKdG1wID0gYXMuZGF0YS5mcmFtZShhZGopICU+JQogICAgdGliYmxlOjpyb3duYW1lc190b19jb2x1bW4oJ3ZhcjEnKSAlPiUKICAgIHBpdm90X2xvbmdlcigtdmFyMSwgbmFtZXNfdG89J3ZhcjInLCB2YWx1ZXNfdG89J3ZhbHVlJykgJT4lCiAgICBtdXRhdGUodmFyMSA9IGZhY3Rvcih2YXIxLCBsZXZlbHM9Y29sbmFtZXMoYWRqKSksCiAgICAgICAgICAgdmFyMiA9IGZhY3Rvcih2YXIyLCBsZXZlbHM9Y29sbmFtZXMoYWRqKSkpCnAxID0gZ2dwbG90KHRtcCkgKwogICAgYWVzKHg9dmFyMSwgeT12YXIyLCBmaWxsPXZhbHVlKSArCiAgICBnZW9tX3RpbGUoKSArCiMgICAgZ2VvbV90ZXh0KGFlcyhsYWJlbD1yb3VuZCh2YWx1ZSwgMikpKSArCiAgICBzY2FsZV9maWxsX2dyYWRpZW50KG5hbWU9IkZlYXR1cmUgUGFpcndpc2VcbkNvLW9jY3VyZW5jZSIsIGxvdz0id2hpdGUiLCBoaWdoPSJyZWQiKSArCiAgICB4bGFiKCIiKSArCiAgICB5bGFiKCIiKSArCiAgICB0aGVtZV9taW5pbWFsKCkgKwogICAgdGhlbWUoYXhpcy50ZXh0LnggPSBlbGVtZW50X3RleHQoYW5nbGU9NjAsIHZqdXN0PTEsIGhqdXN0PTEpKSArCiAgICBjb29yZF9maXhlZCgpCnRtcDIgPSBhZGoKdG1wMltsb3dlci50cmkodG1wMiwgZGlhZz1UKV0gPSBOQQp0bXAgPSBhcy5kYXRhLmZyYW1lKHRtcDIpICU+JQogICAgdGliYmxlOjpyb3duYW1lc190b19jb2x1bW4oJ3ZhcjEnKSAlPiUKICAgIHBpdm90X2xvbmdlcigtdmFyMSwgbmFtZXNfdG89J3ZhcjInLCB2YWx1ZXNfdG89J3ZhbHVlJykgJT4lCiAgICBtdXRhdGUodmFyMSA9IGZhY3Rvcih2YXIxLCBsZXZlbHM9Y29sbmFtZXMoYWRqKSksCiAgICAgICAgICAgdmFyMiA9IGZhY3Rvcih2YXIyLCBsZXZlbHM9Y29sbmFtZXMoYWRqKSkpICU+JQogICAgZmlsdGVyKCFpcy5uYSh2YWx1ZSkpCnAyID0gZ2dwbG90KHRtcCkgKwogICAgZ2VvbV9oaXN0b2dyYW0oYWVzKHg9dmFsdWUpLCBiaW5zPTIwKSArIAogICAgeGxhYignUGFpcndpc2UgQ28tb2NjdXJlbmNlJykgKwogICAgeWxhYignQ291bnQnKSArCiAgICB0aGVtZV9taW5pbWFsKCkKcDEKcDIKYGBgCgpJZ25vcmUgdGhlIGRpYWdvbmFscyBvbiB0aGUgaGVhdG1hcCwgYXMgdGhlc2UgY2FwdHVyZSBlZGdlIGNhc2VzIHdoZXJlIHNvbWV0aW1lcyB0aGUgZm9yZXN0IHNwbGl0cwpvbiB0aGUgc2FtZSB2YXJpYWJsZSBjb25zZWN1dGl2ZWx5LgoKVGhlIGV4YWN0IGZvcm11bGEgZm9yIHBhaXJ3aXNlIGNvLW9jY3VyZW5jZSB1c2VkIGhlcmUgaXM6CgokJApcYmVnaW57ZXF1YXRpb259Clx0ZXh0cm17Q28tb2NjdXJlbmNlfV97aSwgan0gPSBcZnJhY3tcc3VtX3t0IFxpbiBUfSBcc3VtX3tuIFxpbiBOX3t0fX0gSShpIFxpbiBFKG4pKUkoaiBcaW4gRShuKSl9CiAgICB7Zl97aX1mX3tqfX0gLApcZW5ke2VxdWF0aW9ufQokJAoKd2hlcmUKJGkkIGFuZCAkaiQgYXJlIGZlYXR1cmVzLAokZl97aX0kIGlzIHRoZSBjb3VudCBvZiBmZWF0dXJlIGxhYmVsICRpJCBvdmVyIGFsbCBub2RlcyBpbiBhIGZvcmVzdCwKJFQkIGlzIHRoZSBzZXQgb2YgdHJlZXMgaW4gYSBmb3Jlc3QsCiROJCBpcyB0aGUgc2V0IG9mIG5vZGVzIGluIGEgdHJlZSwKJEkkIGlzIHRoZSBpbmRpY2F0b3IgZnVuY3Rpb24sCmFuZAokRSQgaXMgdGhlIHNldCBvZiBlZGdlcyBmb3Igbm9kZSAkbiQuCgpgYGB7ciBjby1vY2N1cmVuY2VfdmFsdWVfdGFibGUsIHN1bW1hcnk9VH0KdG1wICU+JSBhcnJhbmdlKC12YWx1ZSkgJT4lCiAgICBtdXRhdGUodmFsdWU9Zm9ybWF0Qyh2YWx1ZSwgZm9ybWF0PSJlIiwgZGlnaXRzPTMpKQpgYGAKCjxtYXJrPk9ic2VydmF0aW9uczwvbWFyaz4KCi0gQmFzaWMgdW5zdXBlcnZpc2VkIHJhbmRvbSBmb3Jlc3QgYWxnb3JpdGhtCiAgLSBUaGUgYWxnb3JpdGhtIGJ5IGl0c2VsZiBzZWVtcyB0byBzdGlsbCBiZSBhYmxlIHRvIGRpc3Rpbmd1aXNoIGltcG9ydGFudCBhbmQgdW5pbXBvcnRhbnQKICAgIGZlYXR1cmVzLCB3aXRoIHRoZSBNaXRvc2VzIGFuZCBTZXBhbC5XaWR0aCBmZWF0dXJlcyByYW5raW5nIGxlYXN0IGluIGltcG9ydGFuY2UgKGFzIHRoZXkgYXJlIGluCiAgICB0aGUgb3JpZ2luYWwgZGF0YSBzZXRzKS4KICAtIFNldmVyYWwgb2YgdGhlIGJyZWFzdCBjYW5jZXIgZmVhdHVyZXMgc2VlbSB0byBkb21pbmF0ZSB0aGUgZmVhdHVyZSBpbXBvcnRhbmNlIG92ZXIgdGhlIGlyaXMKICAgIGZlYXR1cmVzLgogICAgLSBUaGlzIG1heSBiZSBkdWUgdG8gYnJlYXN0IGNhbmNlciBoYXZpbmcgbW9yZSBmZWF0dXJlcyB0aGFuIGlyaXMKLSBXaXRoIGZlYXR1cmUgY28tb2NjdXJlbmNlIGNhbGN1bGF0aW9uCiAgLSBDby1vY2N1cmVuY2UgYXBwZWFycyB0byBjb3JyZXNwb25kIHdpdGggdGhlIG9yaWdpbmFsIHNlcGFyYXRlIGRhdGEgc2V0cwogIC0gSWYgd2UgZG8gbm90IG5vcm1hbGl6ZSBieSB0aGUgdG90YWwgdGltZXMgZmVhdHVyZXMgb2NjdXIgaW4gdGhlIGZvcmVzdCAoaS5lLiwgcmVtb3ZlIHRoZQogICAgZGVub21pbmF0b3IgaW4gZXF1YXRpb24gKDEpKSwgdGhlbiB0aGUgY2xhc3MgbGFiZWxzIGhhdmUgdGhlIGxlYXN0IGNvLW9jY3VyZW5jZSBjb3VudHMKICAgIC0gbWF5YmUgdGhpcyBpbmRpY2F0ZXMgYSBiaWFzIGFnYWluc3QgY2hvb3NpbmcgY2F0ZWdvcmljYWwgdmFyaWFibGVzIGJ5IHVuc3VwZXJ2aXNlZCByYW5kb20KICAgICAgZm9yZXN0CiAgLSBUaGUgaGlzdG9ncmFtIHNob3dzIGEgYmktIG9yIHRyaS1tb2RhbCBkaXN0cmlidXRpb24sIHdoaWNoIGFnYWluIHN1cHBvcnRzIHRoYXQgdGhlIGZlYXR1cmVzIG9mCiAgICBkaWZmZXJlbnQgZGF0YSBzZXRzIGFyZSBjbHVzdGVyaW5nIHRvZ2V0aGVyCiAgICAtIEJhc2VkIG9uIHRoZSB0YWJsZSB3aXRoIG9yZGVyaW5nLCB3ZSBjYW4gc2VlIHRoYXQgdGhlIGNvbXBhcmlzb25zIGluIHRoZSBzbWFsbGVzdCBtb2RlCiAgICAgIChncmVhdGVyIHRoYW4gNWUtMDYpIGFyZSBiZXR3ZWVuIHRoZSBCcmVhc3RDYW5jZXJcX1xfQ2xhc3MgYW5kIG90aGVyIEJyZWFzdENhbmNlciBmZWF0dXJlcwogICAgICAoY2VsbC5zaXplLCBub3JtYWwubnVjbGVvbGksIGJhcmUubnVjbGVpLCBjZWxsLnNoYXBlLCBhbmQgbWFyZy5hZGhlc2lvbiksIGFuZCBvbmUgY29tcGFyaXNvbgogICAgICBiZXR3ZWVuIGlyaXMgc3BlY2llcyBhbmQgaXJpcyBwZXRhbCB3aWR0aC4KICAgIC0gRXZlcnkgY3Jvc3MgZGF0YSBzZXQgY29tcGFyaXNvbiAoYmV0d2VlbiBhbiBpcmlzIGZlYXR1cmUgYW5kIGEgYnJlYXN0IGNhbmNlciBmZWF0dXJlKSByYW5rcwogICAgICBsb3dlciB0aGFuIHdpdGhpbiBkYXRhIHNldCBjb21wYXJpc29ucywgd2l0aCBhIGN1dG9mZiBhdCA0LjAxMWUtMDYKICAtIFRoZSByYW5raW5ncyBvZiB0aGUgY28tb2NjdXJlbmNlIGJldHdlZW4gZmVhdHVyZXMgb2YgdGhlIHNhbWUgZGF0YSBzZXQgYXBwZWFyIHRvIGJlIGNvbnNpc3RlbnQKICAgIHdpdGggdGhlIGdlbmVyYWwgZmVhdHVyZSBpbXBvcnRhbmNlLCBpLmUuLCBjby1vY2N1cmVuY2UgdmFsdWVzIG9mIHRoZSBpcmlzIHBldGFsIGZlYXR1cmVzIGFyZQogICAgaGlnaGVyIHRoYW4gY28tb2NjdXJlbmNlIHZhbHVlcyBvZiB0aGUgaXJpcyBzZXBhbCBmZWF0dXJlcwotIEl0IG1heSBiZSB1c2VmdWwgdG8gcmVwZWF0IHRoaXMgYW5hbHlzaXMgd2l0aG91dCBpbmNsdWRpbmcgdGhlIHRydWUgY2xhc3MgbGFiZWxzCgojIyMgQ28tb2NjdXJlbmNlIGNsdXN0ZXJpbmcgb2YgZmVhdHVyZXMKCldlIGNhbiBkZWZpbmUgYSBkaXN0YW5jZSBtZWFzdXJlIGJhc2VkIG9uIHRoZSBjby1vY2N1cmVuY2UgYmV0d2VlbiBmZWF0dXJlcyB3aXRoOgoKJCQKXGJlZ2lue2VxdWF0aW9ufQpEaXN0YW5jZV97aSwgan0gPSAxIC0gXGZyYWN7XHRleHRybXtDby1vY2N1cmVuY2V9X3tpLCBqfSB9e1xtYXggKFx0ZXh0cm17Q28tb2NjdXJlbmNlfSl9IC4gClxlbmR7ZXF1YXRpb259CiQkCgpVc2luZyBoaWVyYXJjaGljYWwgY2x1c3RlcmluZywgd2UgY2FuIHNob3cgdGhhdCB0aGUgbGFyZ2VzdCBkaXN0YW5jZSBpcyBiZXR3ZWVuIHRoZSB0d28gZGF0YSBzZXRzLgoKYGBge3IgaWJjX2hpZXJhcmNoaWNhbH0KaWJjLmRpc3QgPSBhcy5kaXN0KDEgLSBhZGovbWF4KGFkaikpCiNpYmMuZGlzdDIgPSBhcy5kaXN0KC0xICogbG9nKGFkaikpCiMgdGhpcyBzZWNvbmQgb25lIGRvZXMgbm90IHdvcmsgdmVyeSB3ZWxsIGF0IGFsbCwgdGhlIGRpc3RhbmNlcyBhdCB0aGUgbGVhdmVzIGFyZSB3YXkgbG9uZ2VyIHRoYW4KIyBhbnkgc2ltaWxhcml0eQpwbG90KGhjbHVzdChpYmMuZGlzdCwgbWV0aG9kID0gIndhcmQuRDIiKSwgaGFuZz0tMSkKYGBgCmBgYHtyIGliY19oY2x1c3RfY2x1c3Rlcl9hc3NpZ25tZW50cywgc3VtbWFyeT1UfQpjdXRyZWUoaGNsdXN0KGliYy5kaXN0KSwgaz0yKQpgYGAKCkxpa2V3aXNlLCBvcHRpY3MgY2FuIGlkZW50aWZ5IGNsdXN0ZXJzIChhbG9uZyB3aXRoIGZlYXR1cmVzIHRoYXQgbWlnaHQgYmUgcmVtb3ZlZCkuCgpgYGB7ciBpYmNfb3B0aWNzX290aGVyX2RldGFpbHMsIHN1bW1hcnk9VH0KI3JvdW5kKHNxcnQobnJvdyhhZGopKSkKb3B0ID0gb3B0aWNzKGliYy5kaXN0LCBtaW5QdHM9MykgIyBJIHRoaW5rIG1pblB0cyBpcyBzZXQgc29tZXdoYXQgYXJiaXRyYXJpbHkgLSBpLmUuLCBob3dldmVyIG1hbnkKIyBmZWF0dXJlcyB5b3UgdGhpbmsgc2hvdWxkIHN1cHBvcnQgYSBnaXZlbiBjbHVzdGVyaW5nIG1pbnVzIDI7IGluIHRoaXMgY2FzZSwgYmVjYXVzZSBpcmlzIG9ubHkgaGFzCiMgNSBmZWF0dXJlcyAoaW5jbHVkaW5nIHRydWUgY2xhc3MgbGFiZWxzLCBpdCdzIGRldGVjdGVkIGJlc3Qgd2hlbiB1c2luZyBtaW5QdHMgPD0gMwppYmMudW1hcCA9IHVtYXA6OnVtYXAoYXMubWF0cml4KGliYy5kaXN0KSwgaW5wdXQ9ImRpc3QiKQp0bXAgPSBhcy5kYXRhLmZyYW1lKGliYy51bWFwJGxheW91dCkgJT4lCiAgICB0aWJibGU6OnJvd25hbWVzX3RvX2NvbHVtbigiZmVhdHVyZSIpCm9wdCA9IGV4dHJhY3RYaShvcHQsIHhpPTAuMDUsIG1pbmltdW09VCkKcGxvdChvcHQpCmBgYApgYGB7ciBpYmNfcGxvdF9vcHRpY3NfdW1hcCwgZmlnLmhlaWdodD03LCBmaWcud2lkdGg9OX0KdG1wJGNsdXN0ZXIgPSBmYWN0b3IoaWZlbHNlKG9wdCRjbHVzdGVyID09IDAsICJ1bmNsdXN0ZXJlZCIsIGFzLmNoYXJhY3RlcihvcHQkY2x1c3RlcikpKQpnZ3Bsb3QodG1wKSArCiAgICBhZXMoeD1WMSwgeT1WMikgKwogICAgZ2VvbV9wb2ludChhZXMoY29sb3I9Y2x1c3RlciksIHNpemU9MykgKwogICAgZ2dyZXBlbDo6Z2VvbV90ZXh0X3JlcGVsKGFlcyhsYWJlbD1mZWF0dXJlKSkgKwogICAgZ2d0aXRsZSgiT1BUSUNTIGNsdXN0ZXJpbmcgd2l0aCBVTUFQIG1hcHBpbmciKSArCiAgICB4bGFiKCd1bWFwIDEnKSArCiAgICB5bGFiKCd1bWFwIDInKSArCiAgICB0aGVtZV9taW5pbWFsKCkKYGBgCgojIyMgV2l0aGluIGNsdXN0ZXIgZmVhdHVyZSBpbXBvcnRhbmNlCgpJIHRoaW5rIHRoZXJlIGFyZSBzZXZlcmFsIHdheXMgd2l0aGluIGNsdXN0ZXIgZmVhdHVyZSBpbXBvcnRhbmNlIG1pZ2h0IGJlIGRlc2NyaWJlZC4gVHdvIG9mIHdoaWNoCkkndmUgZGVzY3JpYmVkIGhlcmU6CgoxLiBVc2UgdGhlIHVuc3VwZXJ2aXNlZCBmZWF0dXJlIGltcG9ydGFuY2UgbGlzdHMgZm9yIGluZGl2aWR1YWwgY2x1c3RlcnMgb2YgZmVhdHVyZXMKMi4gVXNlIHRoZSBhdmVyYWdlIHJhbmsgY28tb2NjdXJlbmNlIGJldHdlZW4gZmVhdHVyZXMgaW4gdGhlIHNhbWUgY2x1c3RlcgoKIyMjIEFJQwoKYGBge3IgaXJpc2JjX3ZhclJlZHVjdF9BSUN9CmltcCA9IGRhdGEuZnJhbWUoaW1wb3J0YW5jZShpcmlzYmNfcmYpKSAlPiUKICAgIGFycmFuZ2UoZGVzYyhNZWFuRGVjcmVhc2VBY2N1cmFjeSkpCnJmcyA9IGNhY2hlX3Jkcyh7CiAgICBsYXBwbHkoMToobnJvdyhpbXApLTEpLCBmdW5jdGlvbihpKSB7CiAgICAgICAgdmFycyA9IHJvd25hbWVzKGltcClbMTppXSAgICAKICAgICAgICB1c3JmKHRlc3QxWyx2YXJzLGRyb3A9Rl0sIG50cmVlPTEwMDAwKQogICAgfSkKfSkKcmZzID0gYyhyZnMsIGxpc3QoaXJpc2JjX3JmKSkKYGBgCmBgYHtyIHBsb3RfaXJpc2JjX3ZhclJlZHVjdF9BSUN9CnlfdHJ1ZSA9IHJmc1tbMV1dJHkKdG1wID0gYmluZF9yb3dzKGxhcHBseShzZXFfYWxvbmcocmZzKSwgZnVuY3Rpb24oaSkgewogICBhaWNfb2JzID0gY2xmQUlDKHlfdHJ1ZVsxOihsZW5ndGgoeV90cnVlKS8yKV0sIAogICAgICAgICAgICAgICAgICAgICAgeV9wcmVkPXJmc1tbaV1dJHZvdGVzWzE6KGxlbmd0aCh5X3RydWUpLzIpLF0sIGs9aSkKICAgYWljID0gY2xmQUlDKHlfdHJ1ZSwgeV9wcmVkPXJmc1tbaV1dJHZvdGVzLCBrPWkpCiAgIGVyciA9IHJmc1tbaV1dJGVyci5yYXRlWzEwMDAwLCAxXQogICB2YXJzID0gbnJvdyhpbXBvcnRhbmNlKHJmc1tbaV1dKSkKICAgZGF0YS5mcmFtZShBSUM9YWljLCBBSUNfb2JzPWFpY19vYnMsIGVycm9yPWVyciwgbnZhcnM9dmFycykKfSkpICU+JSAKICAgIG11dGF0ZShhY3Jvc3MoIW52YXJzLCB+IC54IC8gbWF4KC54KSkpICU+JQogICAgcGl2b3RfbG9uZ2VyKCFjKG52YXJzKSkgJT4lCiAgICBncm91cF9ieShuYW1lKSAlPiUKICAgIG11dGF0ZShpcy5taW4gPSB2YWx1ZSA9PSBtaW4odmFsdWUpKQoKZ2dwbG90KHRtcCkgKwogICAgYWVzKHg9bnZhcnMsIHk9dmFsdWUsIGNvbG9yPW5hbWUpICsKICAgIGdlb21fbGluZShhbHBoYT0wLjUpICsKICAgIGdlb21fcG9pbnQoYWVzKHNoYXBlPWlzLm1pbiksIGFscGhhPTAuNSkgKwogICAgc2NhbGVfY29sb3JfYnJld2VyKG5hbWU9IiIsIHBhbGV0dGU9IkRhcmsyIikgKwogICAgc2NhbGVfeF9jb250aW51b3VzKG5hbWU9Ik51bWJlciBvZiB2YXJpYWJsZXMiLCBicmVha3M9c2NhbGVzOjpicmVha3NfcHJldHR5KDYpLAogICAgICAgICAgICAgICAgICAgICAgIHNlYy5heGlzID0gc2VjX2F4aXMofiAuICogMSwgYnJlYWtzPTE6bnJvdyhpbXApLCBsYWJlbHM9cm93bmFtZXMoaW1wKSkpICsKICAgIHlsaW0oMCwgMSkgKwogICAgeWxhYigiUmVsYXRpdmUgdmFsdWUiKSArCiAgICB0aGVtZV9taW5pbWFsKCkgKwogICAgdGhlbWUoYXhpcy50ZXh0LngudG9wID0gZWxlbWVudF90ZXh0KGFuZ2xlPTYwLCB2anVzdD0wLCBoanVzdD0wKSkKYGBgCgpgYGB7ciBpcmlzYmNfYWljX3dpdGhfY2x1c3RlcnN9CmNsdXMgPSBhcy5kYXRhLmZyYW1lKGliYy51bWFwJGxheW91dCkKY2x1cyRjbHVzdGVyID0gb3B0JGNsdXN0ZXIKI2NsdXMKYWRkX3JmcyA9IGNhY2hlX3Jkcyh7CiAgICBsYXBwbHkoMToyLCBmdW5jdGlvbihpKSB7CiAgICAgICAgdmFycyA9IHJvd25hbWVzKGNsdXMpW2NsdXMkY2x1c3RlciA9PSBpXSAgICAKICAgICAgICB1c3JmKHRlc3QxWyx2YXJzLGRyb3A9Rl0sIG50cmVlPTEwMDAwLCBzZWVkPTQxKQp9KX0sIHJlcnVuPUYsIGNsZWFuPVQpCgp0bXAyID0gYmluZF9yb3dzKGxhcHBseShzZXFfYWxvbmcoYWRkX3JmcyksIGZ1bmN0aW9uKGkpIHsKICAgcmYgPSBhZGRfcmZzW1tpXV0KICAgdmFycyA9IG5yb3coaW1wb3J0YW5jZShyZikpCiAgIGFpY19vYnMgPSBjbGZBSUMoeV90cnVlWzE6KGxlbmd0aCh5X3RydWUpLzIpXSwgCiAgICAgICAgICAgICAgICAgICAgICB5X3ByZWQ9cmYkdm90ZXNbMToobGVuZ3RoKHlfdHJ1ZSkvMiksXSwgaz12YXJzKQogICBhaWMgPSBjbGZBSUMoeV90cnVlLCB5X3ByZWQ9cmYkdm90ZXMsIGs9dmFycykKICAgZXJyID0gcmYkZXJyLnJhdGVbMTAwMDAsIDFdCiAgIGRhdGEuZnJhbWUoQUlDPWFpYywgQUlDX29icz1haWNfb2JzLCBlcnJvcj1lcnIsIG52YXJzPXZhcnMpCn0pKQp0bXAgPSBiaW5kX3Jvd3MobGFwcGx5KHNlcV9hbG9uZyhyZnMpLCBmdW5jdGlvbihpKSB7CiAgIHZhcnMgPSBucm93KGltcG9ydGFuY2UocmZzW1tpXV0pKQogICBhaWNfb2JzID0gY2xmQUlDKHlfdHJ1ZVsxOihsZW5ndGgoeV90cnVlKS8yKV0sIAogICAgICAgICAgICAgICAgICAgICAgeV9wcmVkPXJmc1tbaV1dJHZvdGVzWzE6KGxlbmd0aCh5X3RydWUpLzIpLF0sIGs9dmFycykKICAgYWljID0gY2xmQUlDKHlfdHJ1ZSwgeV9wcmVkPXJmc1tbaV1dJHZvdGVzLCBrPXZhcnMpCiAgIGVyciA9IHJmc1tbaV1dJGVyci5yYXRlWzEwMDAwLCAxXQogICBkYXRhLmZyYW1lKEFJQz1haWMsIEFJQ19vYnM9YWljX29icywgZXJyb3I9ZXJyLCBudmFycz12YXJzKQp9KSkKCnRtcDIkQUlDID0gdG1wMiRBSUMgLyBtYXgodG1wJEFJQykKdG1wMiRBSUNfb2JzID0gdG1wMiRBSUNfb2JzIC8gbWF4KHRtcCRBSUNfb2JzKQp0bXAyJGVycm9yID0gdG1wMiRlcnJvciAvIG1heCh0bXAkZXJyb3IpCgp0bXAgPSB0bXAgJT4lIAogICAgbXV0YXRlKGFjcm9zcyghbnZhcnMsIH4gLnggLyBtYXgoLngpKSkgJT4lCiAgICBwaXZvdF9sb25nZXIoIWMobnZhcnMpKSAlPiUKICAgIGdyb3VwX2J5KG5hbWUpICU+JQogICAgbXV0YXRlKGlzLm1pbiA9IHZhbHVlID09IG1pbih2YWx1ZSkpCnRtcDIgPSB0bXAyICU+JSAKICAgIHBpdm90X2xvbmdlcighYyhudmFycykpICU+JQogICAgbXV0YXRlKGlzLm1pbj1GKSAlPiUKICAgIGZpbHRlcih2YWx1ZSA8PSAxKQoKZ2dwbG90KHRtcCkgKwogICAgZ2VvbV9saW5lKGFlcyh4PW52YXJzLCB5PXZhbHVlLCBjb2xvcj1uYW1lKSwgYWxwaGE9MC41KSArCiAgICBnZW9tX3BvaW50KGFlcyh4PW52YXJzLCB5PXZhbHVlLCBjb2xvcj1uYW1lLCBzaGFwZT1pcy5taW4pLCBhbHBoYT0wLjUpICsKICAgIHNjYWxlX2NvbG9yX2JyZXdlcihuYW1lPSIiLCBwYWxldHRlPSJEYXJrMiIpICsKICAgIHNjYWxlX3hfY29udGludW91cyhuYW1lPSJOdW1iZXIgb2YgdmFyaWFibGVzIiwgYnJlYWtzPXNjYWxlczo6YnJlYWtzX3ByZXR0eSg2KSwKICAgICAgICAgICAgICAgICAgICAgICBzZWMuYXhpcyA9IHNlY19heGlzKH4gLiAqIDEsIGJyZWFrcz0xOm5yb3coaW1wKSwgbGFiZWxzPXJvd25hbWVzKGltcCkpKSArCiAgICB5bGltKDAsIDEpICsKICAgIHlsYWIoIlJlbGF0aXZlIHZhbHVlIikgKwogICAgdGhlbWVfbWluaW1hbCgpICsKICAgIGdlb21fcG9pbnQoZGF0YT10bXAyLCBtYXBwaW5nPWFlcyh4PW52YXJzLCB5PXZhbHVlLCBjb2xvcj1uYW1lKSwgc2hhcGU9Mywgc2l6ZT0zKSArCiAgICB0aGVtZShheGlzLnRleHQueC50b3AgPSBlbGVtZW50X3RleHQoYW5nbGU9NjAsIHZqdXN0PTAsIGhqdXN0PTApKQpgYGAK